Снижение прочности
При построении компилятора сокращение силы — это оптимизация компилятора , при которой дорогостоящие операции заменяются эквивалентными, но менее затратными операциями. [1] Классический пример уменьшения силы преобразует сильные умножения внутри цикла в более слабые сложения – то, что часто происходит при адресации массивов ( Cooper, Simpson & Vick 1995 , стр. 1) .
Примеры снижения силы включают замену умножения внутри цикла сложением и замену возведения в степень внутри цикла умножением.
Анализ кода
[ редактировать ]Большая часть времени выполнения программы обычно занимает небольшой участок кода (называемый « горячей точкой »), и этот код часто находится внутри цикла, который выполняется снова и снова.
Компилятор использует методы для идентификации циклов и распознавания характеристик значений регистров внутри этих циклов. Для снижения прочности компилятор интересуется:
- Инварианты цикла: значения, которые не изменяются внутри тела цикла.
- Индукционные переменные: значения, которые повторяются каждый раз в цикле.
Инварианты цикла по сути являются константами внутри цикла, но их значение может меняться вне цикла. Переменные индукции изменяются на известные величины. Условия относятся к конкретному циклу. Когда циклы вложены, переменная индукции во внешнем цикле может быть инвариантом цикла во внутреннем цикле.
Снижение силы ищет выражения, включающие инвариант цикла и переменную индукции. Некоторые из этих выражений можно упростить. Например, умножение инварианта цикла c и переменная индукции i
с = 7 ; для ( я знак равно 0 ; я < N ; я ++ ) { y [ я ] знак равно c * я ; } можно заменить последовательными более слабыми добавками
с = 7 ; к = 0 ; для ( я знак равно 0 ; я < N ; я ++ ) { y [ я ] знак равно k ; к знак равно к + с ; } Пример снижения прочности
[ редактировать ]Ниже приведен пример, который уменьшит силу всех циклических умножений, возникающих в результате вычислений адреса индексации массива.
Представьте себе простой цикл, который присваивает массиву единичную матрицу .
для ( я знак равно 0 ; я < п ; я ++ ) { для ( j знак равно 0 ; j < п ; j ++ ) { А [ я , j ] = 0,0 ; } А [ я , я ] знак равно 1,0 ; } Промежуточный код
[ редактировать ]Компилятор будет рассматривать этот код как
0010 ; for (i = 0, i < n; i++) 0020 ; { 0030 r1 = #0 ; i = 0 0040 G0000: 0050 нагрузка r2 , n ; i < n 0060 cmp r1 , r2 0070 bge G0001 0080 0090 ; for (j = 0; j < n; j++) 0100 ; { 0110 r3 = #0 ; j = 0 0120 G0002: 0130 нагрузка r4 , n ; j < n 0140 cmp r3 , r4 0150 bge G0003 0160 0170 ; А[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 ; А[i,i] = 1,0; 0300 нагрузка r12 , n ; вычислить нижний индекс i * n + i 0310 r13 = r1 * r12 0320 r14 = r13 + r1 0330 r15 = r14 * #8 ; вычислить адрес байта 0340 fr4 = #1.0 0350 fstore fr4 , A [ r15 ] 0360 0370 ; я++ 0380 r1 = r1 + #1 0390 br 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 ; for (i = 0, i < n; i++) 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 < n 0070 bge G0001 0080 0190 r8 = r1 * r2 ; вычислить нижний индекс i * n 0310 ; r13 = r1*r2 убит; используйте r8 ; вычислить нижний индекс i * n 0090 ; for (j = 0; j < n; j++) 0100 { 0110 r3 = #0 ; j = 0 0120 G0002: 0140 см/с r3 , r2 ; j < n 0150 bge G0003 0160 0170 ; А[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 ; А[i,i] = 1,0; 0320 r14 = r8 + r1 ; вычислить нижний индекс i * n + i 0330 r15 = r14 * #8 ; вычислить адрес байта 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 0380 r1 = r1 + #1 0390 br 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 < n 0145 cmp r9 , r20 ; r8 + j < r8 + n = r20 0150 bge G0003 0160 0170 ; А[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 < r8 + n = r20 0150 bge G0003 0160 0170 ; А[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 < r8 + n = r20 0147 cmp r10 , r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22 0150 bge G0003 0160 0170 ; А[i,j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + #8; уменьшенная прочность умножить 0255 ; r9 = r9 + #1 убит; переменная цикла 0260 br G0002 Внешний цикл
[ редактировать ]Вернемся к общей картине:
0010 ; for (i = 0, i < n; i++) 0020 { 0030 r1 = #0 ; i = 0 0050 нагрузка 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 ; вычислить нижний индекс i * n 0117 r20 = r8 + r2 ; предел 0118 r10 = r8 * #8 ; начальное значение r10 0119 r22 = r20 * #8 ; новый лимит 0090 ; для (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 ; А[i,j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + #8; прочность уменьшена кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; А[i,i] = 1,0; 0320 r14 = r8 + r1 ; вычислить нижний индекс i * n + i 0330 r15 = r14 * #8 ; вычислить адрес байта 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 0380 r1 = r1 + #1 0390 br 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 ; for (i = 0, i < n; i++) 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 ; я < n 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 < n; j++) 0100 { 0120 G0002: 0147 cmp r10 , r22 ; r10 = 8*(r8 + j) < 8*(r8 + n) = r22 0150 bge G0003 0160 0170 ; А[i,j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + #8; прочность уменьшена кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; А[i,i] = 1,0; 0320 r14 = r8 + r1 ; вычислить нижний индекс i * n + i 0330 r15 = r14 * #8 ; вычислить адрес байта 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 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 br G0000 0400 } 0410 G0001: Последнее умножение
[ редактировать ]В результате в двух циклах остается только одна операция умножения (в 0330) во внешнем цикле и никаких умножений во внутреннем цикле.
0010 ; for (i = 0, i < n; i++) 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 < n 0070 bge G0001 0080 0118 r10 = r40 ; сила сниженной экспрессии до r40 0090 ; для (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 ; А[i,j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + #8; прочность уменьшена кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; А[i,i] = 1,0; 0320 r14 = r8 + r1 ; вычислить нижний индекс i * n + i 0330 r15 = r14 * #8 ; вычислить адрес байта 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 0380 r1 = r1 + #1 0385 r8 = r8 + r2 ; уменьшение прочности r8 = r1 * r2 0386 r40 = r40 + r30 ; выражение уменьшения силы r8 * 8 0388 r22 = r22 + r30 ; снижение прочности r22 = r20*8 0390 br G0000 0400 } 0410 G0001: В строке 0320 r14 представляет собой сумму r8 и r1, а r8 и r1 увеличиваются в цикле. Регистр r8 увеличивается на r2 (=n), а в r1 увеличивается на 1. Следовательно, в регистре r14 каждый раз при прохождении цикла увеличивается на n+1. Последнее умножение цикла в 03:30 можно уменьшить, добавляя (r2+1)*8 каждый раз при прохождении цикла.
0010 ; for (i = 0, i < n; i++) 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 r49 = r2 + #1 005 D r50 = r49 * #8 ; приращение уменьшенной прочности 0040 G0000: 0060 cmr r1 , r2 ; i < n 0070 bge G0001 0080 0118 r10 = r40 ; сила сниженной экспрессии до r40 0090 ; для (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 ; А[i,j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + #8; прочность уменьшена кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; А[i,i] = 1,0; 0320 ; r14 = r8 + r1 убит; мертвый код 0330 ; r15 = r14 * #8 убит; прочность снижена 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 0380 r1 = r1 + #1 0385 r8 = г8 + г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 br G0000 0400 } 0410 G0001: Нам еще многое предстоит сделать. Константное свертывание распознает, что r1=0 в преамбуле, поэтому несколько инструкций будут очищены. Регистр r8 в цикле не используется, поэтому он может исчезнуть.
Более того, r1 используется только для управления контуром, поэтому r1 можно заменить другой индукционной переменной, например r40. Там, где я пошел 0 <= i < n, регистр r40 идет 0 <= r40 < 8 * n * n.
0010 ; для (я = 0, я < n; я++) 0020 { 0030 ; р1 = #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 = 0 005 C r49 = r2 + #1 005 D r50 = r49 * #8 ; приращение уменьшенной прочности 005 D r60 = r2 * r30 ; новый лимит для r40 0040 G0000: 0060 ; cmp r1, r2 убит ; я < п; индукционная переменная заменена на 0065 cmp r40 , r60 ; я * 8 * n < 8 * n * n 0070 bge G0001 0080 0118 r10 = r40 ; сила сниженной экспрессии до r40 0090 ; для (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 ; А[i,j] = 0,0; 0230 fstore fr3 , A [ r10 ] 0240 0245 r10 = r10 + #8; сила уменьшена кратно 0260 br G0002 0270 } 0280 G0003: 0290 ; А[i,i] = 1,0; 0350 fstore fr4 , A [ r15 ] 0360 0370 ;i++ 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 br G0000 0400 } 0410 G0001: Другие операции по снижению прочности
[ редактировать ]При сокращении численности операторов используются математические тождества для замены медленных математических операций более быстрыми. Преимущества зависят от целевого ЦП, а иногда и от окружающего кода (который может повлиять на доступность других функциональных блоков внутри ЦП).
- замена целочисленного деления или умножения на степень 2 арифметическим или логическим сдвигом [2]
- замена целочисленного умножения на константу комбинацией сдвигов, сложения или вычитания
- замена целочисленного деления на константу умножением, используя преимущества ограниченного диапазона машинных целых чисел. [3] Этот метод также работает, если делитель не является целым числом, достаточно большим, чем 1, например √2 или π. [4]
| Исходный расчет | Расчет замены |
|---|---|
| у+= 1 | у++ |
| y%2 != 0 | й и 1 |
| у = х * 2 | у = х << 1 |
| у = х/2 | у = х >> 1 |
| у = х % 2 | у = х и 1 |
| у = х * 15 | у = (х << 4) - х |
| у = (uint16_t)x/10 | y = ((uint32_t)x * (uint32_t)0xCCCD) >> 19) |
| y = (uint16_t)x / π | y = (((uint32_t)x * (uint32_t)0x45F3) >> 16) + x) >> 2) |
Индукционная переменная (сирота)
[ редактировать ]Индукционная переменная или рекурсивное уменьшение силы заменяет функцию некоторой систематически изменяющейся переменной более простым расчетом с использованием предыдущих значений функции. В процедурном языке программирования это применимо к выражению, включающему переменную цикла, а в декларативном языке — к аргументу рекурсивной функции . Например,
ж x = ... ( 3 ** x ) ... ( ж ( x + 1 )) ... становится
f x = f' x 1 где f' x z = ... z ... ( f' ( x + 1 ) ( 3 * z )) ... Здесь модифицированная рекурсивная функция f ′ принимает второй параметр z = 3 ** x, позволяя заменить дорогостоящее вычисление (3 ** x) более дешевым (3 * z).
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Стивен Мучник; Мучник и партнеры (15 августа 1997 г.). Расширенная реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2 .
Снижение силы.
- ^ В таких языках, как C и Java, целочисленное деление имеет семантику округления к нулю, тогда как битовый сдвиг всегда округляется в меньшую сторону, что требует особого подхода к отрицательным числам. Например, в Java
-3 / 2оценивается как-1, тогда как-3 >> 1оценивается как-2. Таким образом, в этом случае компилятор не может оптимизировать деление на два, заменяя его битовым сдвигом. - ^ Гранлунд, Торбьёрн; Питер Л. Монтгомери. «Деление на инвариантные целые числа с использованием умножения» (PDF) .
- ^ Джонс, Найджел. «Деление целых чисел на константы» . Архивировано из оригинала 26 марта 2024 года.
Ссылки
[ редактировать ]- Ахо, Альфред В .; Сетхи, Рави ; Уллман, Джеффри Д. (1986), Составители: принципы, методы и инструменты (2-е изд.), ISBN 978-0-201-10088-4
- Аллен, Фрэнсис Э .; Кок, Джон ; Кеннеди, Кен (1981), «Снижение силы оператора», в Мюнхнике, Стивен С.; Джонс, Нил Д. (ред.), Анализ потока программы: теория и приложения , Prentice-Hall, ISBN 978-0-13-729681-1
- Кок, Джон ; Кеннеди, Кен (ноябрь 1977 г.), «Алгоритм снижения силы оператора», Communications of the ACM , 20 (11): 850–856, doi : 10.1145/359863.359888 , S2CID 1092505
- Купер, Кейт; Симпсон, Тейлор; Вик, Кристофер (октябрь 1995 г.), Снижение силы оператора (PDF) , Университет Райса , получено 22 апреля 2010 г.