En informática , la selección de instrucciones es la etapa de un compilador backend 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 pseudoregistros (a menudo conocidos como temporales ) y todavía puede estar (y normalmente está) sujeto a optimización de mirilla . De lo contrario, se parece mucho al código de máquina , al código de bytes o al lenguaje ensamblador de destino .
Por ejemplo, para la siguiente secuencia de código IR de nivel medio
t1 = unt2 = bt3 = t1 + t2a = t3b = t1
una buena secuencia de instrucciones para la arquitectura x86 es
MOV EAX , a XCHG EAX , b AÑADIR a , EAX
Para obtener una encuesta completa sobre la selección de instrucciones, consulte. [1] [2]
Macroexpansión
El enfoque más simple para la selección de instrucciones se conoce como macro expansión [3] o generación de código interpretativo . [4] [5] [6] Un selector de instrucciones de expansión macro opera 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 apropiadas. La expansión 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 primero en profundidad. [9] En este último, 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 normalmente genera código ineficiente. Para mitigar esta limitación, los compiladores que aplican este enfoque normalmente lo combinan con 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 enfoque de Davidson-Fraser y se aplica actualmente en GCC . [10]
Cobertura de gráficos
Otro enfoque es transformar primero el IR de nivel medio en un gráfico y luego cubrir el gráfico usando patrones . Un patrón es una plantilla que coincide con una parte del gráfico y se puede implementar con una única 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 gráficos en forma de árbol, la cobertura de menor costo se puede encontrar en tiempo lineal usando 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 o métodos codiciosos. de la optimización combinatoria. [12] [13] [14]
Referencias
- ^ Blindell, Gabriel S. Hjort (2013). Encuesta sobre selección de instrucción: una revisión de la literatura 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. Saltador. doi :10.1007/978-3-319-34019-7. ISBN 978-3-319-34017-3. S2CID 13390131.
- ^ Marrón, P. (1969). "Un estudio sobre macroprocesadores". Revisión Anual en Programación Automática . 6 (2): 37–88. doi :10.1016/0066-4138(69)90001-9. ISSN 0066-4138.
- ^ Cattell, RGG (1979). "Un estudio y crítica de algunos modelos de generación de código" (PDF) . Facultad de Ciencias de la Computación, Universidad Carnegie Mellon (Informe técnico). Archivado (PDF) desde el original el 23 de mayo de 2019.
- ^ Ganapathi, M.; Fischer, CN; Hennessy, JL (1982). "Generación de código compilador reorientable". Encuestas Informáticas . 14 (4): 573–592. doi :10.1145/356893.356897. ISSN 0360-0300. S2CID 2361347.
- ^ Lunell, H. (1983). Sistemas de escritura 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 máquina para lenguajes de programación de alto nivel (Tesis doctoral). Ithaca, Nueva York, Estados Unidos: Universidad de Cornell.
- ^ Davidson, JW; Fraser, CW (1984). "Selección de código mediante optimización de código objeto". Transacciones ACM sobre lenguajes y sistemas de programación . 6 (4): 505–526. CiteSeerX 10.1.1.76.3796 . doi :10.1145/1780.1783. ISSN 0164-0925. S2CID 10315537.
- ^ Ah, AV; Ganapathi, M.; Tjiang, SWK (1989). "Generación de código mediante coincidencia de árboles y programación dinámica". Transacciones ACM sobre lenguajes y sistemas de programación . 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 Séptimo 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. S2CID 14384424.
- ^ 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. S2CID 5513238.
- ^ Floch, A.; Wolinski, C.; Kuchcinski, K. (2010). "Selección combinada de instrucciones y programación para procesadores con estructura celular reconfigurable". Actas de la 21ª Conferencia Internacional sobre Arquitecturas y Procesadores de Aplicaciones Específicas (ASAP'10) : 167–174.
enlaces externos
