En informática , la selección de instrucciones es la etapa de un compilador backend que transforma su representación intermedia de nivel medio (IR) en un 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 pseudo-registros (a menudo conocidos como temporales ) y aún puede estar, y generalmente está, sujeto a optimización de mirilla . De lo contrario, se parece mucho a la meta de código de máquina , el código de bytes , o en 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 obtener una encuesta completa sobre la selección de instrucciones, consulte. [1]
Expansión macro
El enfoque más simple para la selección de instrucciones se conoce como macro expansión [2] o generación de código interpretativo . [3] [4] [5] Un selector de instrucciones de macroexpansión funciona haciendo coincidir plantillas en el IR de nivel medio. Tras una coincidencia, se ejecuta la macro correspondiente , utilizando la parte correspondiente del IR como entrada, que emite las instrucciones de destino adecuadas. La expansión macro se puede hacer directamente en la representación textual del IR de nivel medio, [6] [7] o el IR se puede transformar primero en una representación gráfica que luego se recorre en profundidad primero. [8] 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 macro de forma aislada generalmente genera código ineficiente. Para mitigar esta limitación, los compiladores que aplican este enfoque generalmente lo combinan 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 de Davidson-Fraser y actualmente se aplica en GCC . [9]
Cobertura de gráficos
Otro enfoque es transformar primero el IR de nivel medio en una representación gráfica 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 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 , [10] pero para los DAG y los 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. [11] [12] [13]
Estrategia de mínimo común denominador
La estrategia de mínimo común denominador es una técnica de selección de instrucciones que se utiliza en plataformas donde existen instrucciones suplementarias al procesador para hacer que los programas ejecutables sean portátiles en una amplia gama de computadoras. Bajo una estrategia de mínimo común denominador, el comportamiento predeterminado del compilador es construir para la mínima arquitectura común. El uso de cualquier extensión de procesador disponible está desactivado de forma predeterminada, a menos que se active explícitamente mediante interruptores de línea de comando.
El uso de una estrategia de mínimo común denominador significa que las instrucciones y capacidades complementarias del procesador no se utilizan de forma predeterminada.
Referencias
- ^ Hjort Blindell, Gabriel (2016). Selección de instrucción: principios, métodos y aplicaciones . Saltador. doi : 10.1007 / 978-3-319-34019-7 . ISBN 978-3-319-34017-3.
- ^ Brown, P. (1969). "Una encuesta de 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). "Una encuesta y crítica de algunos modelos de generación de código" (PDF) . Escuela de Ciencias de la Computación, Universidad Carnegie Mellon (Informe técnico).
- ^ Ganapathi, M .; Fischer, CN; Hennessy, JL (1982). "Generación de código de compilador retargetable". Encuestas de Computación . 14 (4): 573–592. doi : 10.1145 / 356893.356897 . ISSN 0360-0300 .
- ^ Lunell, H. (1983). Sistemas de escritura de generador 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 .
- ^ Wilcox, TR (1971). Generación de código 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 de 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 .
- ^ Aho, AV; Ganapathi, M .; Tjiang, SWK (1989). "Generación de código mediante programación dinámica y concordancia de árboles". Transacciones ACM sobre lenguajes y sistemas de programación . 11 (4): 491–516. CiteSeerX 10.1.1.456.9102 . doi : 10.1145 / 69558.75700 .
- ^ 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 de Síntesis de Alto Nivel (ISSS'94) . págs. 70–75. CiteSeerX 10.1.1.521.8288 . doi : 10.1109 / ISHLS.1994.302339 . ISBN 978-0-8186-5785-6.
- ^ Bashford, Steven; Leupers, Rainer (1999). "Selección de código impulsada por restricciones para DSPS de punto fijo". Actas de la 36a conferencia ACM / IEEE sobre la conferencia de 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.
- ^ Floch, A .; Wolinski, C .; Kuchcinski, K. (2010). "Selección de instrucciones y programación combinada para procesadores con tejido celular reconfigurable". Actas de la 21ª Conferencia internacional sobre arquitecturas y procesadores de aplicaciones específicas (ASAP'10) : 167-174.
enlaces externos
- Formas alternativas de admitir diferentes generaciones de computadoras [ enlace muerto permanente ]