En la construcción del compilador , la reducción de la fuerza es una optimización del compilador en la que las operaciones costosas se reemplazan por operaciones equivalentes pero menos costosas. [1] El ejemplo clásico de reducción de fuerza convierte las multiplicaciones "fuertes" dentro de un bucle en adiciones "más débiles", algo que ocurre con frecuencia en el direccionamiento de matrices. ( Cooper, Simpson y Vick 1995 , p. 1)
Los ejemplos de reducción de fuerza incluyen:
- reemplazar una multiplicación dentro de un ciclo con una suma
- reemplazar una exponenciación dentro de un ciclo con una multiplicación
Análisis de código
La mayor parte del tiempo de ejecución de un programa normalmente se gasta en una pequeña sección de código (denominada zona activa ), y ese código suele estar dentro de un bucle que se ejecuta una y otra vez.
Un compilador usa métodos para identificar bucles y reconocer las características de los valores de registro dentro de esos bucles. Para la reducción de la fuerza, el compilador está interesado en:
- Invariantes de bucle: los valores que no cambian dentro del cuerpo de un bucle.
- Variables de inducción: los valores que se iteran cada vez a través del ciclo.
Los invariantes de bucle son esencialmente constantes dentro de un bucle, pero su valor puede cambiar fuera del bucle. Las variables de inducción están cambiando en cantidades conocidas. Los términos son relativos a un bucle en particular. Cuando los bucles están anidados, una variable de inducción en el bucle externo puede ser invariante en el bucle interno.
La reducción de fuerza busca expresiones que involucren un invariante de bucle y una variable de inducción. Algunas de esas expresiones se pueden simplificar. Por ejemplo, la multiplicación de invariante de bucle c
y variable de induccióni
c = 7 ; para ( i = 0 ; i < N ; i ++ ) { y [ i ] = c * i ; }
se puede reemplazar con adiciones sucesivas más débiles
c = 7 ; k = 0 ; para ( i = 0 ; i < N ; i ++ ) { y [ i ] = k ; k = k + c ; }
Ejemplo de reducción de fuerza
A continuación se muestra un ejemplo que reducirá la fuerza de todas las multiplicaciones de bucles que surgieron de los cálculos de direcciones de indexación de matrices.
Imagine un bucle simple que establece una matriz en la matriz de identidad .
para ( i = 0 ; i < n ; i ++ ) { para ( j = 0 ; j < n ; j ++ ) { A [ i , j ] = 0.0 ; } A [ i , i ] = 1.0 ; }
Código intermedio
El compilador verá este código como
0010 ; para (i = 0, i ;>0020 ; { 0030 r1 = # 0 ; i = 0 0040 G0000: 0050 carga r2 , n ; i 0060 cmp r1 , r2 0070 bge G0001 0080 0090 ; para (j = 0; j ;>0100 ; { 0110 r3 = # 0 ; j = 0 0120 G0002: 0130 carga r4 , n ; j 0140 cmp r3 , r4 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0180 carga r7 , n 0190 r8 = r1 * r7 ; calcular el subíndice i * n + j 0200 r9 = r8 + r3 0210 r10 = r9 * # 8 ; calcular la dirección del byte 0220 fr3 = # 0.0 0230 fstore fr3 , A [ r10 ] 0240 0250 r3 = r3 + # 1 ; j ++ 0260 br G0002 0270 ; } 0280 G0003: 0290 ; A [i, i] = 1,0; 0300 carga r12 , n ; Calcular subíndice i * n + i 0310 r13 = r1 * r12 0320 r14 = r13 + r1 0330 r15 = r14 * # 8 ; calcular la dirección de byte 0340 fr4 = # 1.0 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 r1 = r1 + # 1 0390 br G0000 0400 ; } 0410 G0001:
Esto expresa la matriz A bidimensional como una matriz unidimensional de tamaño n * n, de modo que siempre que el código de alto nivel exprese A [x, y] será internamente A [(x * n) + y] para cualquier dados índices válidos xey.
Muchas optimizaciones
El compilador comenzará a realizar muchas optimizaciones, no solo reducción de fuerza. Expresiones que son constantes (invariante) dentro de un bucle serán izadas fuera del bucle. Las constantes se pueden cargar fuera de ambos bucles, como los registros de coma flotante fr3 y fr4. El reconocimiento de que algunas variables no cambian permite fusionar los registros; n es constante, por lo que r2, r4, r7, r12 pueden elevarse y colapsarse. El valor común i * n se calcula en (el izado) r8 y r13, por lo que colapsan. El bucle más interno (0120-0260) se ha reducido de 11 a 7 instrucciones intermedias. La única multiplicación que permanece en el bucle más interno es la multiplicación de la línea 0210 por 8.
0010 ; para (i = 0, i ;>0020 { 0030 r1 = # 0 ; i = 0 0050 carga r2 , n 0130 ; carga r4, n muerto; utilice r2 0180 ; carga r7, n muerto; utilice r2 0300 ; carga r12, n muerto; utilice r2 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0190 r8 = r1 * r2 ; calcular el subíndice i * n 0310 ; r13 = r1 * r2 muerto; use r8; calcular el subíndice i * n 0090 ; para (j = 0; j ;>0100 { 0110 r3 = # 0 ; j = 0 0120 G0002: 0140 cmp r3 , r2 ; j 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0200 r9 = r8 + r3 ; calcular el subíndice i * n + j 0210 r10 = r9 * # 8 ; calcular la dirección del byte 0230 fstore fr3 , A [ r10 ] 0240 0250 r3 = r3 + # 1 ; j ++ 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; Calcular subíndice i * n + i 0330 r15 = r14 * # 8 ; calcular la dirección de byte 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 r1 = r1 + # 1 0390 br G0000 0400 } 0410 G0001:
Hay más optimizaciones por hacer. El registro r3 es la variable principal en el bucle más interno (0140-0260); se incrementa en 1 cada vez que pasa por el bucle. El registro r8 (que es invariante en el ciclo más interno) se agrega a r3. En lugar de usar r3, el compilador puede eliminar r3 y usar r9. El lazo, en lugar de ser controlado por r3 = 0 a n-1, puede ser controlado por r9 = r8 + 0 a r8 + n-1. Eso agrega cuatro instrucciones y elimina cuatro instrucciones, pero hay una instrucción menos dentro del ciclo.
0110 ; r3 = # 0 muerto; j = 0 0115 r9 = r8 ; nueva asignación 0117 r20 = r8 + r2 ; nuevo límite 0120 G0002: 0140 ; cmp r3, r2 muerto; j 0145 cmp r9 , r20 ; r8 + j 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0200 ; r9 = r8 + r3 muerto; calcular el subíndice i * n + j 0210 r10 = r9 * # 8 ; calcular la dirección del byte 0230 fstore fr3 , A [ r10 ] 0240 0250 ; r3 = r3 + # 1 muerto; j ++ 0255 r9 = r9 + # 1 ; nueva variable de bucle 0260 br G0002
Ahora r9 es la variable de ciclo, pero interactúa con multiplicar por 8. Aquí podemos hacer una reducción de fuerza. La multiplicación por 8 se puede reducir a algunas sumas sucesivas de 8. Ahora no hay multiplicaciones dentro del ciclo.
0115 r9 = r8 ; nueva asignación 0117 r20 = r8 + r2 ; nuevo límite 0118 r10 = r8 * # 8 ; valor inicial de r10 0120 G0002: 0145 cmp r9 , r20 ; r8 + j 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0210 ; r10 = r9 * # 8 muerto; calcular la dirección del byte 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0255 r9 = r9 + # 1 ; variable de bucle 0260 br G0002
Los registros r9 y r10 (= 8 * r9) no son necesarios; r9 se puede eliminar en el ciclo. El ciclo ahora tiene 5 instrucciones.
0115 ; r9 = r8 muerto 0117 r20 = r8 + r2 ; límite 0118 r10 = r8 * # 8 ; valor inicial de r10 0119 r22 = r20 * # 8 ; nuevo límite 0120 G0002: 0145 ; cmp r9, r20 muerto; r8 + j 0147 cmp r10 , r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r22 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0255 ; r9 = r9 + # 1 muerto; variable de bucle 0260 br G0002
Bucle exterior
Volver a la imagen completa:
0010 ; para (i = 0, i ;>0020 { 0030 r1 = # 0 ; i = 0 0050 carga r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0190 r8 = r1 * r2 ; calcular el subíndice i * n 0117 r20 = r8 + r2 ; límite 0118 r10 = r8 * # 8 ; valor inicial de r10 0119 r22 = r20 * # 8 ; nuevo límite 0090 ; para (j = 0; j ;>0100 { 0120 G0002: 0147 cmp r10 , r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r22 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; Calcular subíndice i * n + i 0330 r15 = r14 * # 8 ; calcular la dirección de byte 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 r1 = r1 + # 1 0390 br G0000 0400 } 0410 G0001:
Ahora hay cuatro multiplicaciones dentro del ciclo externo que incrementa r1. Se puede reducir la fuerza del registro r8 = r1 * r2 en 0190 configurándolo antes de ingresar al bucle (0055) e incrementándolo en r2 en la parte inferior del bucle (0385).
Se puede reducir la fuerza del valor r8 * 8 (en 0118) inicializándolo (0056) y agregando 8 * r2 cuando r8 se incrementa (0386).
El registro r20 se incrementa por la invariante / constante r2 cada vez que pasa por el bucle en 0117. Después de ser incrementado, se multiplica por 8 para crear r22 en 0119. Esa multiplicación se puede reducir sumando 8 * r2 cada vez a través del bucle. .
0010 ; para (i = 0, i ;>0020 { 0030 r1 = # 0 ; i = 0 0050 carga r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 r8 = r1 * r2 ; establecer el valor inicial para r8 0056 r40 = r8 * # 8 ; valor inicial para r8 * 8 0057 r30 = r2 * # 8 ; incrementar para r40 0058 r20 = r8 + r2 ; copiado de 0117 0058 R22 = R20 * # 8 ; valor inicial de r22 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0190 ; r8 = r1 * r2 muerto; calcular el subíndice i * n 0117 ; r20 = r8 + r2 muerto - código muerto 0118 r10 = r40 ; resistencia reducida expresión a r40 0119 ; r22 = r20 * # 8 muerto; fuerza reducida 0090 ; para (j = 0; j ;>0100 { 0120 G0002: 0147 cmp r10 , r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r22 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; Calcular subíndice i * n + i 0330 r15 = r14 * # 8 ; calcular la dirección de byte 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 r1 = r1 + # 1 0385 r8 = r8 + r2 ; fuerza reducir r8 = r1 * r2 0386 r40 = r40 + r30 ; fuerza reducir la expresión r8 * 8 0388 r22 = r22 + r30 ; fuerza reducir r22 = r20 * 8 0390 br G0000 0400 } 0410 G0001:
La última multiplicación
Eso deja a los dos bucles con solo una operación de multiplicación (en 0330) dentro del bucle externo y sin multiplicaciones dentro del bucle interno.
0010 ; para (i = 0, i ;>0020 { 0030 r1 = # 0 ; i = 0 0050 carga r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 r8 = r1 * r2 ; establecer el valor inicial para r8 0056 r40 = r8 * # 8 ; valor inicial para r8 * 8 0057 r30 = r2 * # 8 ; incrementar para r40 0058 r20 = r8 + r2 ; copiado de 0117 0058 R22 = R20 * # 8 ; valor inicial de r22 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0118 r10 = r40 ; fuerza expresión reducida a r40 0090 ; para (j = 0; j ;>0100 { 0120 G0002: 0147 cmp r10 , r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r22 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; Calcular subíndice i * n + i 0330 r15 = r14 * # 8 ; calcular la dirección de byte 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 r1 = r1 + # 1 0385 r8 = r8 + r2 ; fuerza reducir r8 = r1 * r2 0386 r40 = r40 + r30 ; fuerza reducir la expresión r8 * 8 0388 r22 = r22 + r30 ; fuerza reducir r22 = r20 * 8 0390 br G0000 0400 } 0410 G0001:
En la línea 0320, r14 es la suma de r8 y r1, y r8 y r1 se incrementan en el ciclo. El registro r8 está siendo golpeado por r2 (= n) y r1 está siendo golpeado por 1. En consecuencia, r14 está siendo golpeado por n + 1 cada vez que pasa por el bucle. Se puede reducir la fuerza de la última multiplicación de bucle a las 0330 agregando (r2 + 1) * 8 cada vez que pasa por el bucle.
0010 ; para (i = 0, i ;>0020 { 0030 r1 = # 0 ; i = 0 0050 carga r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 r8 = r1 * r2 ; establecer el valor inicial para r8 0056 r40 = r8 * # 8 ; valor inicial para r8 * 8 0057 r30 = r2 * # 8 ; incrementar para r40 0058 r20 = r8 + r2 ; copiado de 0117 0058 R22 = R20 * # 8 ; valor inicial de r22 005 A r14 = r8 + r1 ; copiado de 0320 005 B r15 = r14 * # 8 ; valor inicial de r15 (0330) 005 C r4 9 = r2 + # 1 005 D r50 = r4 9 * # 8 ; incremento de fuerza reducida 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0118 r10 = r40 ; fuerza expresión reducida a r40 0090 ; para (j = 0; j ;>0100 { 0120 G0002: 0147 cmp r10 , r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r22 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 ; r14 = r8 + r1 muerto; código muerto 0330 ; r15 = r14 * # 8 muerto; fuerza reducida 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 r1 = r1 + # 1 0385 r8 = r8 + r2 ; fuerza reducir r8 = r1 * r2 0386 r40 = r40 + r30 ; fuerza reducir la expresión r8 * 8 0388 r22 = r22 + r30 ; fuerza reducir r22 = r20 * 8 0389 r15 = r15 + r50 ; fuerza reducir r15 = r14 * 8 0390 br G0000 0400 } 0410 G0001:
Aún queda mucho por hacer. El plegado constante reconocerá que r1 = 0 en el preámbulo, por lo que varias instrucciones se limpiarán. El registro r8 no se usa en el bucle, por lo que puede desaparecer.
Además, r1 solo se usa para controlar el bucle, por lo que r1 se puede reemplazar por una variable de inducción diferente, como r40. Donde fui 0 <= i
0010 ; para (i = 0, i ;>0020 { 0030 ; r1 = # 0; i = 0, se convierte en código muerto 0050 carga r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 ; r8 = # 0 muerto; r8 ya no se usa 0056 r40 = # 0 ; valor inicial para r8 * 8 0057 r30 = r2 * # 8 ; incremento para r40 0058 ; r20 = r2 muerto; R8 = 0, se convierte en el código muerto 0058 r22 = r2 * # 8 ; r20 = r2 005 A ; r14 = # 0 muerto; r8 = 0, se convierte en código muerto 005 B r15 = # 0 ; r14 = 0 005 C r4 9 = r2 + # 1 005 D r50 = r4 9 * # 8 ; incremento de fuerza reducida 005 D r60 = r2 * r30 ; nuevo límite para r40 0040 G0000: 0060 ; cmp r1, r2 muerto; i variable de inducción reemplazada ;>0065 cmp r40 , r60 ; i * 8 * n <8 * n * n 0070 bge G0001 0080 0118 r10 = r40 ; fuerza expresión reducida a r40 0090 ; para (j = 0; j ;>0100 { 0120 G0002: 0147 cmp r10 , r22 ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r22 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; fuerza reducida multiplicar 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0350 fstore fr4 , A [ r15 ] 0360 0370 ; i ++ 0380 ; r1 = r1 + # 1 muerto; código muerto (r40 controla el lazo) 0385 ; r8 = r8 + r2 muerto; código muerto 0386 r40 = r40 + r30 ; fuerza reducir la expresión r8 * 8 0388 r22 = r22 + r30 ; fuerza reducir r22 = r20 * 8 0389 r15 = r15 + r50 ; fuerza reducir r15 = r14 * 8 0390 br G0000 0400 } 0410 G0001:
Otras operaciones de reducción de fuerza
- Este material está en disputa. Se describe mejor como optimización de mirilla y asignación de instrucciones .
La reducción de la fuerza del operador utiliza identidades matemáticas para reemplazar las operaciones matemáticas lentas con operaciones más rápidas. Los beneficios dependen de la CPU de destino y, a veces, del código circundante (que puede afectar la disponibilidad de otras unidades funcionales dentro de la CPU).
- reemplazar la división o multiplicación de enteros por una potencia de 2 con un desplazamiento aritmético o lógico [2]
- reemplazar la multiplicación de números enteros por una constante con una combinación de cambios, sumas o restas
- reemplazando la división de enteros por una constante con una multiplicación, aprovechando el rango limitado de enteros de máquina. [3] Este método también funciona si el divisor es un número no entero suficientemente mayor que 1, por ejemplo, √2 o π. [4]
Cálculo original | Cálculo de reemplazo |
---|---|
y = x / 8 | y = x >> 3 |
y = x * 64 | y = x << 6 |
y = x * 2 | y = x << 1 |
y = x * 15 | y = (x << 4) - x |
y = x / 10 (donde x es de tipo uint16_t) | y = ((uint32_t) x * (uint32_t) 0xCCCD) >> 19) |
y = x / π (donde x es de tipo uint16_t) | y = (((uint32_t) x * (uint32_t) 0x45F3) >> 16) + x) >> 2) |
Variable de inducción (huérfana)
La variable de inducción o la reducción de la fuerza recursiva reemplaza una función de alguna variable que cambia sistemáticamente con un cálculo más simple utilizando valores anteriores de la función. En un lenguaje de programación procedimental, esto se aplicaría a una expresión que involucra una variable de bucle y en un lenguaje declarativo se aplicaría al argumento de una función recursiva . Por ejemplo,
f x = ... ( 3 ** x ) ... ( f ( x + 1 )) ...
se convierte en
f x = f ' x 1 donde f' x z = ... z ... ( f ' ( x + 1 ) ( 3 * z )) ...
Aquí la función recursiva modificada f ′ toma un segundo parámetro z = 3 ** x, permitiendo que el cálculo costoso (3 ** x) sea reemplazado por el más barato (3 * z).
Ver también
Notas
- ^ Steven Muchnick; Muchnick y Asociados (15 de agosto de 1997). Implementación avanzada del diseño del compilador . Morgan Kaufmann. ISBN 978-1-55860-320-2.
Reducción de fuerza.
- ^ En lenguajes como C y Java, la división de enteros tiene una semántica de redondeo hacia cero, mientras que un desplazamiento de bits siempre redondea hacia abajo, lo que requiere un tratamiento especial para los números negativos. Por ejemplo, en Java,
-3 / 2
evalúa a-1
, mientras que-3 >> 1
evalúa a-2
. Entonces, en este caso, el compilador no puede optimizar la división por dos reemplazándola por un cambio de bit. - ^ Granlund, Torbjörn; Peter L. Montgomery. "División por números enteros invariantes mediante la multiplicación" (PDF) .
- ^ Jones, Nigel. "División de enteros por constantes" .
Referencias
- Aho, Alfred V .; Sethi, Ravi ; Ullman, Jeffrey D. (1986), Compiladores: Principios, técnicas y herramientas (2a ed.), ISBN 978-0-201-10088-4
- Allen, Francis E .; Cocke, John ; Kennedy, Ken (1981), "Reducción de la fuerza del operador", en Munchnik, Steven S .; Jones, Neil D. (eds.), Program Flow Analysis: Theory and Applications , Prentice-Hall, ISBN 978-0-13-729681-1
- Cocke, John ; Kennedy, Ken (noviembre de 1977), "Un algoritmo para la reducción de la fuerza del operador", Comunicaciones del ACM , 20 (11), doi : 10.1145 / 359863.359888
- Cooper, Keith; Simpson, Taylor; Vick, Christopher (octubre de 1995), Operator Strength Reduction (PDF) , Rice University , consultado el 22 de abril de 2010
Este artículo se basa en material extraído del Diccionario gratuito de informática en línea antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.