В компиляторе конструкции , снижение прочности является оптимизацией компилятора , где дорогостоящие операции заменяются эквивалентными , но менее дорогие операциями. [1] Классический пример уменьшения силы преобразует «сильные» умножения внутри цикла в «более слабые» сложения - то, что часто происходит при адресации массивов. ( Купер, Симпсон и Вик, 1995 , стр. 1)
Примеры снижения прочности включают:
- замена умножения в цикле на сложение
- замена возведения в степень в цикле умножением
Анализ кода
Большая часть времени выполнения программы обычно тратится на небольшой участок кода (называемый горячей точкой ), и этот код часто находится внутри цикла, который выполняется снова и снова.
Компилятор использует методы для идентификации циклов и распознавания характеристик значений регистров в этих циклах. Для снижения прочности компилятор интересует:
- Инварианты цикла: значения, которые не изменяются в теле цикла.
- Индукционные переменные: значения, которые повторяются каждый раз в цикле.
Инварианты цикла по сути являются константами внутри цикла, но их значение может изменяться вне цикла. Индукционные переменные изменяются на известные величины. Условия относятся к конкретному циклу. Когда циклы вложены, индукционная переменная во внешнем цикле может быть инвариантом цикла во внутреннем цикле.
Снижение силы ищет выражения, включающие инвариант цикла и индукционную переменную. Некоторые из этих выражений можно упростить. Например, умножение инварианта цикла c
и переменной индукцииi
c = 7 ; для ( я = 0 ; я < N ; я ++ ) { у [ я ] = с * я ; }
можно заменить последовательными более слабыми добавками
c = 7 ; k = 0 ; для ( я = 0 ; я < N ; я ++ ) { у [ я ] = k ; к = к + с ; }
Пример снижения прочности
Ниже приведен пример, который сократит все циклы умножения, возникающие в результате вычислений адреса индексации массива.
Представьте себе простой цикл, который устанавливает массив в единичную матрицу .
for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { A [ i , j ] = 0,0 ; } A [ i , i ] = 1.0 ; }
Промежуточный код
Компилятор будет рассматривать этот код как
0010 ; для (я = 0, я <п; я ++) 0020 ; { 0030 r1 = # 0 ; i = 0 0040 G0000: 0050 нагрузка r2 , n ; i 0060 cmp r1 , r2 0070 bge G0001 0080 0090 ; для (j = 0; j ;>0100 ; { 0110 r3 = # 0 ; J = 0 0120 G0002: 0130 нагрузки r4 , п ; j 0140 cmp r3 , r4 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0180 нагрузка r7 , n 0190 r8 = r1 * r7 ; вычислить индекс i * n + j 0200 r9 = r8 + r3 0210 r10 = r9 * # 8 ; вычислить адрес байта 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 нагрузка r12 , н ; вычислить индекс i * n + i 0310 r13 = r1 * r12 0320 r14 = r13 + r1 0330 r15 = r14 * # 8 ; вычислять адрес байта 0340 FR4 = # 1.0 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 r1 = r1 + # 1 0390 уш G0000 0400 ; } 0410 G0001:
Это выражает двумерный массив A как одномерный массив размера n * n, так что всякий раз, когда код высокого уровня выражает A [x, y], он будет внутренне A [(x * n) + y] для любого заданы допустимые индексы x и y.
Множество оптимизаций
Компилятор начнет делать множество оптимизаций - не только сокращение силы. Выражения , которые являются постоянными (инвариант) в пределах цикла будет поднят из петли. Константы можно загружать вне обоих циклов, например, в регистры с плавающей запятой fr3 и fr4. Признание того, что некоторые переменные не изменяются, позволяет объединять регистры; n является постоянным, поэтому r2, r4, r7, r12 можно поднимать и свертывать. Общее значение i * n вычисляется в (поднятых) r8 и r13, поэтому они схлопываются. Самый внутренний цикл (0120-0260) был сокращен с 11 до 7 промежуточных инструкций. Единственное умножение, которое остается во внутреннем цикле, - это умножение строки 0210 на 8.
0010 ; для (я = 0, я <п; я ++) 0020 { 0030 r1 = # 0 ; i = 0 0050 нагрузка r2 , n 0130 ; нагрузка r4, n убит; используйте r2 0180 ; нагрузка r7, n убит; используйте r2 0300 ; нагрузка r12, n убит; используйте r2 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0190 r8 = r1 * r2 ; вычислить индекс i * n 0310 ; r13 = r1 * r2 убито; используйте r8; вычислить индекс i * n 0090 ; для (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 ; вычислить индекс i * n + j 0210 r10 = r9 * # 8 ; вычислить адрес байта 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 ; вычислить индекс i * n + i 0330 r15 = r14 * # 8 ; вычислять адрес байта 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 r1 = r1 + # 1 0390 бр G0000 0400 } 0410 G0001:
Есть еще несколько оптимизаций. Регистр r3 - это основная переменная в самом внутреннем цикле (0140-0260); он увеличивается на 1 каждый раз в цикле. Регистр r8 (который является инвариантным для внутреннего цикла) добавляется к r3. Вместо использования r3 компилятор может исключить r3 и использовать r9. Контуром вместо того, чтобы управлять с помощью r3 = 0 до n-1, можно управлять с помощью r9 = r8 + 0 до r8 + n-1. Это добавляет четыре инструкции и уничтожает четыре инструкции, но внутри цикла на одну инструкцию меньше.
0110 ; r3 = # 0 убито; j = 0 0115 r9 = r8 ; новое присвоение 0117 r20 = r8 + r2 ; новый лимит 0120 G0002: 0140 ; cmp r3, r2 убит; j 0145 cmp r9 , r20 ; r8 + j 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0200 ; r9 = r8 + r3 убито; вычислить индекс i * n + j 0210 r10 = r9 * # 8 ; вычислить адрес байта 0230 fstore fr3 , A [ r10 ] 0240 0250 ; r3 = r3 + # 1 убито; j ++ 0255 r9 = r9 + # 1 ; новая переменная цикла 0260 br G0002
Теперь r9 - это переменная цикла, но она взаимодействует с умножением на 8. Здесь мы можем немного уменьшить силу. Умножение на 8 можно свести к нескольким последовательным прибавлениям 8. Теперь внутри цикла нет умножений.
0115 r9 = r8 ; новое присвоение 0117 r20 = r8 + r2 ; новый лимит 0118 r10 = r8 * # 8 ; начальное значение r10 0120 G0002: 0145 cmp r9 , r20 ; r8 + j 0150 bge G0003 0160 0170 ; A [i, j] = 0,0; 0210 ; r10 = r9 * # 8 убито; вычислить адрес байта 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + # 8 ; сила уменьшена умножить 0255 r9 = r9 + # 1 ; переменная петли 0260 br G0002
Регистры r9 и r10 (= 8 * r9) не нужны; r9 можно исключить в цикле. В цикле теперь 5 инструкций.
0115 ; r9 = r8 убит 0117 r20 = r8 + r2 ; предел 0118 r10 = r8 * # 8 ; начальное значение r10 0119 r22 = r20 * # 8 ; новый лимит 0120 G0002: 0145 ; cmp r9, r20 убитый; 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 ; сила уменьшена умножить 0255 ; r9 = r9 + # 1 убито; переменная петли 0260 br G0002
Внешняя петля
Вернемся ко всей картине:
0010 ; для (я = 0, я <п; я ++) 0020 { 0030 r1 = # 0 ; i = 0 0050 нагрузка 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 ; вычислить индекс i * n 0117 r20 = r8 + r2 ; предел 0118 r10 = r8 * # 8 ; начальное значение r10 0119 r22 = r20 * # 8 ; новый лимит 0090 ; для (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 ; сила уменьшенная кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; вычислить индекс i * n + i 0330 r15 = r14 * # 8 ; вычислять адрес байта 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 r1 = r1 + # 1 0390 бр G0000 0400 } 0410 G0001:
Теперь во внешнем цикле есть четыре умножения, увеличивающих r1. Регистр r8 = r1 * r2 в 0190 можно уменьшить, установив его перед входом в цикл (0055) и увеличив его на r2 внизу цикла (0385).
Значение r8 * 8 (0118) можно уменьшить, инициализировав его (0056) и добавив к нему 8 * r2 при увеличении r8 (0386).
Регистр r20 увеличивается на инвариант / константу r2 каждый раз в цикле 0117. После увеличения он умножается на 8, чтобы создать r22 в 0119. Это умножение можно уменьшить, добавляя 8 * r2 каждый раз в цикле. .
0010 ; для (я = 0, я <п; я ++) 0020 { 0030 r1 = # 0 ; i = 0 0050 нагрузка r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 r8 = r1 * r2 ; установить начальное значение для r8 0056 r40 = r8 * # 8 ; начальное значение для r8 * 8 0057 r30 = r2 * # 8 ; приращение для r40 0058 r20 = r8 + r2 ; скопировано из 0117 0058 r22 = r20 * # 8 ; начальное значение r22 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0190 ; r8 = r1 * r2 убито; вычислить индекс i * n 0117 ; r20 = r8 + r2 убит - мертвый код 0118 r10 = r40 ; сила уменьшила экспрессию до r40 0119 ; r22 = r20 * # 8 убито; прочность уменьшена 0090 ; для (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 ; сила уменьшенная кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; вычислить индекс i * n + i 0330 r15 = r14 * # 8 ; вычислять адрес байта 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 r1 = r1 + # 1 0385 r8 = r8 + г2 ; снижение прочности r8 = r1 * r2 0386 r40 = r40 + r30 ; Сила снижения экспрессии r8 * 8 0388 R22 = R22 + R30 ; Сила уменьшить R22 = r20 * 8 0390 бр G0000 0400 } 0410 G0001:
Последнее умножение
Это оставляет два цикла только с одной операцией умножения (на 0330) во внешнем цикле и без умножений во внутреннем цикле.
0010 ; для (я = 0, я <п; я ++) 0020 { 0030 r1 = # 0 ; i = 0 0050 нагрузка r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 r8 = r1 * r2 ; установить начальное значение для r8 0056 r40 = r8 * # 8 ; начальное значение для r8 * 8 0057 r30 = r2 * # 8 ; приращение для r40 0058 r20 = r8 + r2 ; скопировано из 0117 0058 r22 = r20 * # 8 ; начальное значение r22 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0118 r10 = r40 ; прочность уменьшила экспрессию до r40 0090 ; для (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 ; сила уменьшенная кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 r14 = r8 + r1 ; вычислить индекс i * n + i 0330 r15 = r14 * # 8 ; вычислять адрес байта 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 r1 = r1 + # 1 0385 r8 = r8 + г2 ; снижение прочности r8 = r1 * r2 0386 r40 = r40 + r30 ; Сила снижения экспрессии r8 * 8 0388 R22 = R22 + R30 ; Сила уменьшить R22 = r20 * 8 0390 бр G0000 0400 } 0410 G0001:
В строке 0320 r14 представляет собой сумму r8 и r1, а r8 и r1 увеличиваются в цикле. Регистр r8 увеличивается на r2 (= n), а r1 - на 1. Следовательно, r14 увеличивается на n + 1 каждый раз в цикле. Последнее умножение цикла в 0330 может быть уменьшено, добавляя (r2 + 1) * 8 каждый раз в цикле.
0010 ; для (я = 0, я <п; я ++) 0020 { 0030 r1 = # 0 ; i = 0 0050 нагрузка r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 r8 = r1 * r2 ; установить начальное значение для r8 0056 r40 = r8 * # 8 ; начальное значение для r8 * 8 0057 r30 = r2 * # 8 ; приращение для r40 0058 r20 = r8 + r2 ; скопировано из 0117 0058 r22 = r20 * # 8 ; начальное значение r22 005 A r14 = r8 + r1 ; скопировано из 0320 005 B r15 = r14 * # 8 ; начальное значение r15 (0330) 005 C r4 9 = r2 + # 1 005 D r50 = r4 9 * # 8 ; усиление уменьшенное приращение 0040 G0000: 0060 cmp r1 , r2 ; i 0070 bge G0001 0080 0118 r10 = r40 ; прочность уменьшила экспрессию до r40 0090 ; для (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 ; сила уменьшенная кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0320 ; r14 = r8 + r1 убито; мертвый код 0330 ; r15 = r14 * # 8 убито; Сила уменьшена 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 r1 = r1 + # 1 0385 r8 = r8 + г2 ; снижение прочности r8 = r1 * r2 0386 r40 = r40 + r30 ; Сила снижения экспрессии r8 * 8 0388 R22 = R22 + R30 ; снижение прочности r22 = r20 * 8 0389 r15 = r15 + r50 ; Сила уменьшить r15 = r14 * 8 0390 бр G0000 0400 } 0410 G0001:
Есть еще кое-что, что нужно сделать. Постоянное сворачивание распознает, что r1 = 0 в преамбуле, поэтому несколько инструкций будут очищены. Регистр r8 в цикле не используется, поэтому он может исчезнуть.
Кроме того, r1 используется только для управления контуром, поэтому r1 можно заменить другой переменной индукции, такой как r40. Где я пошел 0 <= i
0010 ; для (я = 0, я <п; я ++) 0020 { 0030 ; r1 = # 0; i = 0, становится мертвым кодом 0050 load r2 , n 0220 fr3 = # 0.0 0340 fr4 = # 1.0 0055 ; r8 = # 0 убито; r8 больше не используется 0056 r40 = # 0 ; начальное значение для r8 * 8 0057 r30 = r2 * # 8 ; инкремент для r40 0058 ; r20 = r2 убит; r8 = 0, становится мертвым кодом 0058 r22 = r2 * # 8 ; r20 = r2 005 А ; r14 = # 0 убито; r8 = 0, становится мертвым кодом 005 B r15 = # 0 ; r14 = 005 C r4 9 = r2 + # 1 005 D r50 = r4 9 * # 8 ; сила уменьшенная приращение 005 D r60 = r2 * r30 ; новый лимит для r40 0040 G0000: 0060 ; cmp r1, r2 убит; я <п; индукционная переменная заменена 0065 cmp r40 , r60 ; i * 8 * n <8 * n * n 0070 bge G0001 0080 0118 r10 = r40 ; прочность уменьшила экспрессию до r40 0090 ; для (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 ; сила уменьшенная кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; A [i, i] = 1,0; 0350 fstore FR4 , [ r15 ] 0360 0370 ; я ++ 0380 ; r1 = r1 + # 1 убито; мертвый код (контур управления r40) 0385 ; r8 = r8 + r2 убито; мертвый код 0386 r40 = r40 + r30 ; Сила снижения экспрессии r8 * 8 0388 R22 = R22 + R30 ; снижение прочности r22 = r20 * 8 0389 r15 = r15 + r50 ; Сила уменьшить r15 = r14 * 8 0390 бр G0000 0400 } 0410 G0001:
Прочие операции по снижению силы
- Этот материал является спорным. Лучше это описать как оптимизацию глазком и назначение инструкций .
Снижение силы оператора использует математические тождества для замены медленных математических операций более быстрыми операциями. Преимущества зависят от целевого ЦП, а иногда и от окружающего кода (который может повлиять на доступность других функциональных блоков ЦП).
- замена целочисленного деления или умножения на степень двойки арифметическим сдвигом или логическим сдвигом [2]
- замена целочисленного умножения на константу комбинацией сдвигов, сложений или вычитаний
- замена целочисленного деления на константу умножением с использованием ограниченного диапазона машинных целых чисел. [3] Этот метод также работает, если делитель является нецелым числом, достаточно большим, чем 1, например √2 или π. [4]
Исходный расчет | Расчет замены |
---|---|
у = х / 8 | у = х >> 3 |
у = х * 64 | у = х << 6 |
у = х * 2 | у = х << 1 |
у = х * 15 | у = (х << 4) - х |
y = x / 10 (где x имеет тип uint16_t) | y = ((uint32_t) x * (uint32_t) 0xCCCD) >> 19) |
y = x / π (где x имеет тип uint16_t) | y = (((uint32_t) x * (uint32_t) 0x45F3) >> 16) + x) >> 2) |
Индукционная переменная (сирота)
Индукционная переменная или рекурсивное уменьшение силы заменяет функцию некоторой систематически изменяющейся переменной более простым вычислением с использованием предыдущих значений функции. В процедурном языке программирования это применимо к выражению, содержащему переменную цикла, а на декларативном языке - к аргументу рекурсивной функции . Например,
е х = ... ( 3 ** х ) ... ( е ( х + 1 )) ...
становится
f x = f ' x 1, где f' x z = ... z ... ( f ' ( x + 1 ) ( 3 * z )) ...
Здесь модифицированная рекурсивная функция f ' принимает второй параметр z = 3 ** x, позволяя заменить дорогостоящие вычисления (3 ** x) более дешевыми (3 * z).
Смотрите также
Заметки
- ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Продвинутая реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2.
Снижение силы.
- ^ В таких языках, как C и Java, целочисленное деление имеет семантику округления до нуля, тогда как битовый сдвиг всегда округляется в меньшую сторону, что требует специальной обработки отрицательных чисел. Например, в Java
-3 / 2
оценивается-1
как, тогда как-3 >> 1
оцениваетсякак-2
. Таким образом, в этом случае компилятор не может оптимизировать деление на два, заменив его битовым сдвигом. - ^ Гранлунд, Торбьёрн; Питер Л. Монтгомери. «Деление на инвариантные целые числа с помощью умножения» (PDF) .
- ^ Джонс, Найджел. «Деление целых чисел на константы» .
Рекомендации
- Ахо, Альфред В .; Сетхи, Рави ; Ульман, Джеффри Д. (1986), Компиляторы: принципы, методы и инструменты (2-е изд.), ISBN 978-0-201-10088-4
- Аллен, Фрэнсис Э .; Кок, Джон ; Кеннеди, Кен (1981), «Снижение силы оператора», в Munchnik, Steven S .; Джонс, Нил Д. (ред.), Анализ потока программы: теория и приложения , Прентис-Холл, ISBN 978-0-13-729681-1
- Кок, Джон ; Кеннеди, Кен (ноябрь 1977), "Алгоритм для уменьшения силы оператора", коммуникации ACM , 20 (11), DOI : 10,1145 / 359863,359888
- Купер, Кит; Симпсон, Тейлор; Вик, Кристофер (октябрь 1995 г.), Operator Strength Reduction (PDF) , Университет Райса , получено 22 апреля 2010 г.
Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.