Reducción de fuerza

Optimización del compilador

En la construcción de compiladores , la reducción de fuerza es una optimización del compilador en la que las operaciones costosas se reemplazan con 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 bucle con una suma y reemplazar una exponenciación dentro de un bucle con una multiplicación.

Análisis de código

La mayor parte del tiempo de ejecución de un programa normalmente se consume en una pequeña sección de código (llamada punto activo ), y ese código suele estar dentro de un bucle que se ejecuta una y otra vez.

Un compilador utiliza métodos para identificar bucles y reconocer las características de los valores de registro dentro de esos bucles. Para reducir 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 bucle.

Los invariantes de bucle son, en esencia, constantes dentro de un bucle, pero su valor puede cambiar fuera del bucle. Las variables de inducción cambian 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 un invariante de bucle 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 del invariante de bucle cy la variable de induccióni

c = 7 ; para ( i = 0 ; i < N ; i ++ ) { y [ i ] = c * i ; }              

Puede reemplazarse 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 bucle que surgieron de los cálculos de direcciones de indexación de matrices.

Imagine un bucle simple que establece una matriz en la matriz 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 < n; i++) 0020 ; { 0030 r1 = #0 ; i = 0 0040 G0000: 0050 cargar r2 , n ; i < n 0060 cmp r1 , r2 0070 bge G0001 0080 0090 ; para (j = 0; j < n; j++) 0100 ; { 0110 r3 = #0 ; j = 0 0120 G0002: 0130 cargar r4 , n ; j < n 0140 cmp r3 , r4 0150 bge G0003 0160 0170 ; A[i,j] = 0.0; 0180 cargar r7 , n 0190 r8 = r1 * r7 ; calcular subíndice i * n + j 0200 r9 = r8 + r3 0210 r10 = r9 * #8; calcular dirección de 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 cargar r12 , n ; calcular subíndice i * n + i 0310 r13 = r1 * r12 0320 r14 = r13 + r1 0330 r15 = r14 * #8 ; calcular 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 bidimensional A como una matriz unidimensional de tamaño n*n, de modo que siempre que el código de alto nivel exprese A[x, y] internamente será A[(x*n)+y] para cualquier índice válido x e y.

Muchas optimizaciones

El compilador comenzará a realizar muchas optimizaciones, no solo una reducción de fuerza. Las expresiones que son constantes (invariantes) dentro de un bucle se sacarán del bucle. Las constantes se pueden cargar fuera de ambos bucles, como los registros de punto flotante fr3 y fr4. El reconocimiento de que algunas variables no cambian permite que se fusionen los registros; n es constante, por lo que r2, r4, r7, r12 se pueden elevar y contraer. El valor común i*n se calcula en r8 y r13 (elevados), 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 por 8 de la línea 0210.

0010 ; para (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 cargar r2 , n 0130 ; cargar r4, n eliminado; usar r2 0180 ; cargar r7, n eliminado; usar r2 0300 ; cargar r12, n eliminado; usar r2 0220 fr3 = #0.0 0340 fr4 = #1.0 0040 G0000: 0060 cmp r1 , r2 ; i < n 0070 bge G0001 0080 0190 r8 = r1 * r2 ; calcular subíndice i * n 0310 ; r13 = r1 * r2 eliminado; usar r8; calcular subíndice i * n 0090 ; para (j = 0; j < n; j++) 0100 { 0110 r3 = #0; j = 0 0120 G0002: 0140 cmp r3 , r2 ; j < n 0150 bge G0003 0160 0170 ; A[i,j] = 0.0; 0200 r9 = r8 + r3 ; calcular subíndice i * n + j 0210 r10 = r9 * #8; calcular dirección de 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 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 se pasa por el bucle. El registro r8 (que es invariante en el bucle más interno) se agrega a r3. En lugar de usar r3, el compilador puede eliminar r3 y usar r9. El bucle, 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 bucle.

0110 ; r3 = #0 eliminado ; j = 0 0115 r9 = r8 ; nueva asignación 0117 r20 = r8 + r2 ; nuevo límite 0120 G0002: 0140 ; ​​cmp r3, r2 eliminado ; j < n 0145 cmp r9 , r20 ; r8 + j < r8 + n = r20 0150 bge G0003 0160 0170 ; A[i,j] = 0.0; 0200 ; r9 = r8 + r3 eliminado ; calcular subíndice i * n + j 0210 r10 = r9 * #8 ; calcular dirección de byte 0230 fstore fr3 , A [ r10 ] 0240 0250 ; r3 = r3 + #1 eliminado ; j++ 0255 r9 = r9 + #1 ; nueva variable de bucle 0260 br G0002                                     

Ahora r9 es la variable del bucle, pero interactúa con la multiplicación 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 bucle.

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 < r8 + n = r20 0150 bge G0003 0160 0170 ; A[i,j] = 0.0; 0210 ; r10 = r9 * #8 eliminado ; calcular dirección de 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 del bucle. El bucle ahora tiene 5 instrucciones.

0115 ; r9 = r8 eliminado 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 eliminado ; r8 + j < r8 + n = r20 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 eliminado ; variable de bucle 0260 br G0002                                     

Bucle exterior

Volviendo al panorama completo:

0010 ; para (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 cargar r2 , n 0220 fr3 = #0.0 0340 fr4 = #1.0 0040 G0000: 0060 cmp r1 , r2 ; i < n 0070 bge G0001 0080 0190 r8 = r1 * r2 ; calcular 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 < n; 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 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 bucle externo que incrementa r1. Se puede reducir la fuerza del registro r8 = r1*r2 en 0190 estableciéndolo antes de ingresar al bucle (0055) e incrementándolo en r2 en la parte inferior del bucle (0385).

El valor r8*8 (en 0118) se puede reducir en fuerza inicializándolo (0056) y agregándole 8*r2 cuando se incrementa r8 (0386).

El registro r20 se incrementa por la constante/invariante r2 cada vez que pasa por el bucle en 0117. Después de incrementarse, se multiplica por 8 para crear r22 en 0119. Esa multiplicación se puede reducir en fuerza sumando 8*r2 cada vez que pasa por el bucle.

0010 ; para (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 cargar r2 , n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 r8 = r1 * r2 ; establecer valor inicial para r8 0056 r40 = r8 * #8 ; valor inicial para r8 * 8 0057 r30 = r2 * #8 ; incremento para r40 0058 r20 = r8 + r2 ; copiado de 0117 0058 r22 = r20 * #8 ; valor inicial de r22 0040 G0000: 0060 cmp r1 , r2 ; i < n 0070 bge G0001 0080 0190 ; r8 = r1 * r2 muerto ; calcular subíndice i * n 0117 ; r20 = r8 + r2 muerto - código muerto 0118 r10 = r40 ; expresión de fuerza reducida a r40 0119 ; r22 = r20 * #8 muerto ; fuerza reducida 0090 ; para (j = 0; j < n; 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 dirección de byte 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 0380 r1 = r1 + #1 0385 r8 = r8 +                                                                                                       r2 ; reducción de fuerza r8 = r1 * r2 0386 r40 = r40 + r30 ; expresión de reducción de fuerza r8 * 8 0388 r22 = r22 + r30 ; reducción de fuerza r22 = r20 * 8 0390 br G0000 0400 } 0410 G0001:                 

La última multiplicación

Esto deja los dos bucles con solo una operación de multiplicación (a las 0330) dentro del bucle externo y sin multiplicaciones dentro del bucle interno.

0010 ; para (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 cargar r2 , n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 r8 = r1 * r2 ; establecer valor inicial para r8 0056 r40 = r8 * #8 ; valor inicial para r8 * 8 0057 r30 = r2 * #8 ; incremento para r40 0058 r20 = r8 + r2 ; copiado de 0117 0058 r22 = r20 * #8 ; valor inicial de r22 0040 G0000: 0060 cmp r1 , r2 ; i < n 0070 bge G0001 0080 0118 r10 = r40 ; expresión de fuerza reducida a r40 0090 ; para (j = 0; j < n; 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 dirección de byte 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 0380 r1 = r1 + #1 0385 r8 = r8 + r2 ; fuerza reducida r8 = r1 * r2 0386 r40 = r40 + r30 ; expresión de reducción de fuerza r8 * 8 0388 r22 =                                                                                                              r22 + r30 ; reducción de fuerza 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 bucle. El registro r8 se incrementa en r2 (=n) y r1 se incrementa en 1. En consecuencia, r14 se incrementa en n+1 cada vez que pasa por el bucle. La última multiplicación del bucle en 0330 se puede reducir en fuerza sumando (r2+1)*8 cada vez que pasa por el bucle.

0010 ; para (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 cargar r2 , n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 r8 = r1 * r2 ; establecer valor inicial para r8 0056 r40 = r8 * #8 ; valor inicial para r8 * 8 0057 r30 = r2 * #8 ; incremento 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 r49 = r2 + #1 005 D r50 = r49 * #8; incremento de fuerza reducida 0040 G0000: 0060 cmp r1 , r2 ; i < n 0070 bge G0001 0080 0118 r10 = r40 ; expresión de fuerza reducida a r40 0090 ; para (j = 0; j < n; 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 ; reducción de fuerza r8 = r1 * r2 0386 r40 = r40 + r30 ; expresión de reducción de fuerza r8 * 8 0388 r22 = r22 + r30 ; reducción de fuerza r22 = r20 * 8 0389 r15 = r15 + r50 ; reducción de fuerza 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 lo limpiarán. El registro r8 no se utiliza en el bucle, por lo que puede desaparecer.

Además, r1 solo se utiliza para controlar el bucle, por lo que r1 se puede reemplazar por una variable de inducción diferente, como r40. Donde i pasó a 0 <= i < n, el registro r40 pasa a 0 <= r40 < 8 * n * n.

0010 ; para (i = 0, i < n; i++) 0020 { 0030 ; r1 = #0 ; i = 0, se convierte en código muerto 0050 cargar r2 , n 0220 fr3 = #0.0 0340 fr4 = #1.0 0055 ; r8 = #0 eliminado ; r8 ya no se usa 0056 r40 = #0 ; valor inicial para r8 * 8 0057 r30 = r2 * #8 ; incremento para r40 0058 ; r20 = r2 eliminado ; r8 = 0, se convierte en código muerto 0058 r22 = r2 * #8 ; r20 = r2 005 A ; r14 = #0 eliminado ; r8 = 0, se convierte en código muerto 005 B r15 = #0; r14 = 0 005 C r49 = r2 + #1 005 D r50 = r49 * #8; incremento de fuerza reducida 005 D r60 = r2 * r30 ; nuevo límite para r40 0040 G0000: 0060 ; cmp r1, r2 eliminado; i < n; variable de inducción reemplazada 0065 cmp r40 , r60 ; i * 8 * n < 8 * n * n 0070 bge G0001 0080 0118 r10 = r40 ; expresión de fuerza reducida a r40 0090 ; para (j = 0; j < n; 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 eliminado; código muerto (r40 controla el bucle) 0385 ; r8 = r8 + r2 eliminado; código muerto 0386 r40 = r40 + r30 ; expresión de reducción de fuerza r8 * 8 0388 r22 = r22 + r30 ; reducción de fuerza r22 = r20 * 8 0389 r15 = r15 + r50 ; reducción de fuerza r15 = r14 * 8 0390 br G0000 0400 } 0410 G0001:                       

Otras operaciones de reducción de fuerza

La reducción de la fuerza del operador utiliza identidades matemáticas para reemplazar operaciones matemáticas lentas por 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 números 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 desplazamientos, sumas o restas
• reemplazando la división entera por una constante con una multiplicación, aprovechando el rango limitado de números enteros de la 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]

Variable de inducción (huérfana)

La variable de inducción o reducción de fuerza recursiva reemplaza una función de alguna variable que cambia sistemáticamente con un cálculo más simple que utiliza 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, lo que permite reemplazar el cálculo costoso (3 ** x) por el más económico (3 * z).

Véase también

• Raíz cuadrada inversa rápida
• El deleite del hacker
• Evaluación parcial

Notas

1. Steven Muchnick; Muchnick and Associates (15 de agosto de 1997). Implementación del diseño avanzado de compiladores . Morgan Kaufmann. ISBN 978-1-55860-320-2. Reducción de fuerza.
2. En lenguajes como C y Java, la división de números 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 / 2se evalúa como -1, mientras que -3 >> 1se evalúa como -2. Por lo tanto, en este caso, el compilador no puede optimizar la división por dos reemplazándola por un desplazamiento de bits.
3. Granlund, Torbjörn; Peter L. Montgomery. "División por números enteros invariantes mediante multiplicación" (PDF) .
4. Jones, Nigel. «División de números enteros por constantes». Archivado desde el original el 26 de marzo de 2024.

Referencias

• Aho, Alfred V. ; Sethi, Ravi ; Ullman, Jeffrey D. (1986), Compiladores: principios, técnicas y herramientas (2.ª 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.), Análisis del flujo de programas: teoría y aplicaciones , 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", Communications of the ACM , 20 (11): 850–856, doi : 10.1145/359863.359888 , S2CID  1092505
• Cooper, Keith; Simpson, Taylor; Vick, Christopher (octubre de 1995), Reducción de la fuerza del operador (PDF) , Rice University , consultado el 22 de abril de 2010