Снижение прочности
При построении компилятора сокращение силы — это оптимизация компилятора , при которой дорогостоящие операции заменяются эквивалентными, но менее затратными операциями. [1] Классический пример уменьшения силы преобразует сильные умножения внутри цикла в более слабые сложения – то, что часто происходит при адресации массивов ( Cooper, Simpson & Vick 1995 , стр. 1) .
Примеры снижения силы включают замену умножения внутри цикла сложением и замену возведения в степень внутри цикла умножением.
Анализ кода
[ редактировать ]Большая часть времени выполнения программы обычно занимает небольшой участок кода (называемый « горячей точкой »), и этот код часто находится внутри цикла, который выполняется снова и снова.
Компилятор использует методы для идентификации циклов и распознавания характеристик значений регистров внутри этих циклов. Для снижения прочности компилятор интересуется:
- Инварианты цикла: значения, которые не изменяются внутри тела цикла.
- Индукционные переменные: значения, которые повторяются каждый раз в цикле.
Инварианты цикла по сути являются константами внутри цикла, но их значение может меняться вне цикла. Переменные индукции изменяются на известные величины. Условия относятся к конкретному циклу. Когда циклы вложены, переменная индукции во внешнем цикле может быть инвариантом цикла во внутреннем цикле.
Снижение силы ищет выражения, включающие инвариант цикла и переменную индукции. Некоторые из этих выражений можно упростить. Например, умножение инварианта цикла c и индукционная переменная i
c = 7;
for (i = 0; i < N; i++)
{
y[i] = c * i;
}
можно заменить последовательными более слабыми добавками
c = 7;
k = 0;
for (i = 0; i < N; i++)
{
y[i] = k;
k = k + c;
}
Пример снижения прочности
[ редактировать ]Ниже приведен пример, который уменьшит силу всех циклических умножений, возникающих в результате вычислений адреса индексации массива.
Представьте себе простой цикл, который присваивает массиву единичную матрицу .
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
A[i,j] = 0.0;
}
A[i,i] = 1.0;
}
Промежуточный код
[ редактировать ]Компилятор будет рассматривать этот код как
0010 ; for (i = 0, i < n; i++)
0020 ; {
0030 r1 = #0 ; i = 0
0040 G0000:
0050 load 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 load r4, n ; j < n
0140 cmp r3, r4
0150 bge G0003
0160
0170 ; A[i,j] = 0.0;
0180 load r7, n
0190 r8 = r1 * r7 ; calculate subscript i * n + j
0200 r9 = r8 + r3
0210 r10 = r9 * #8 ; calculate byte address
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 load r12, n ; calculate subscript i * n + i
0310 r13 = r1 * r12
0320 r14 = r13 + r1
0330 r15 = r14 * #8 ; calculate byte address
0340 fr4 = #1.0
0350 fstore fr4, A[r15]
0360
0370 ; i++
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 load r2, n
0130 ; load r4, n killed; use r2
0180 ; load r7, n killed; use r2
0300 ; load r12, n killed; use 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 ; calculate subscript i * n
0310 ; r13 = r1 * r2 killed; use r8 ; calculate subscript i * n
0090 ; for (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 ; calculate subscript i * n + j
0210 r10 = r9 * #8 ; calculate byte address
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 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
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 killed ; j = 0
0115 r9 = r8 ; new assignment
0117 r20 = r8 + r2 ; new limit
0120 G0002:
0140 ; cmp r3, r2 killed ; 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 killed ; calculate subscript i * n + j
0210 r10 = r9 * #8 ; calculate byte address
0230 fstore fr3, A[r10]
0240
0250 ; r3 = r3 + #1 killed ; j++
0255 r9 = r9 + #1 ; new loop variable
0260 br G0002
Теперь r9 — это переменная цикла, но она взаимодействует с умножением на 8. Здесь мы можем немного уменьшить силу. Умножение на 8 можно свести к нескольким последовательным сложениям 8. Теперь внутри цикла умножений нет.
0115 r9 = r8 ; new assignment
0117 r20 = r8 + r2 ; new limit
0118 r10 = r8 * #8 ; initial value of 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 killed ; calculate byte address
0230 fstore fr3, A[r10]
0240
0245 r10 = r10 + #8 ; strength reduced multiply
0255 r9 = r9 + #1 ; loop variable
0260 br G0002
Регистры r9 и r10 (= 8*r9) не нужны; r9 можно исключить в цикле. Цикл теперь состоит из 5 инструкций.
0115 ; r9 = r8 killed
0117 r20 = r8 + r2 ; limit
0118 r10 = r8 * #8 ; initial value of r10
0119 r22 = r20 * #8 ; new limit
0120 G0002:
0145 ; cmp r9, r20 killed ; 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 ; strength reduced multiply
0255 ; r9 = r9 + #1 killed ; loop variable
0260 br G0002
Внешний цикл
[ редактировать ]Вернемся к общей картине:
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load 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 ; calculate subscript i * n
0117 r20 = r8 + r2 ; limit
0118 r10 = r8 * #8 ; initial value of r10
0119 r22 = r20 * #8 ; new limit
0090 ; for (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 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
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 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0190 ; r8 = r1 * r2 killed ; calculate subscript i * n
0117 ; r20 = r8 + r2 killed - dead code
0118 r10 = r40 ; strength reduced expression to r40
0119 ; r22 = r20 * #8 killed ; strength reduced
0090 ; for (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 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0390 br G0000
0400 }
0410 G0001:
Последнее умножение
[ редактировать ]В результате в двух циклах остается только одна операция умножения (в 03:30) во внешнем цикле и никаких умножений во внутреннем цикле.
0010 ; for (i = 0, i < n; i++)
0020 {
0030 r1 = #0 ; i = 0
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0118 r10 = r40 ; strength reduced expression to r40
0090 ; for (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 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 r14 = r8 + r1 ; calculate subscript i * n + i
0330 r15 = r14 * #8 ; calculate byte address
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce 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 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 r8 = r1 * r2 ; set initial value for r8
0056 r40 = r8 * #8 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 r20 = r8 + r2 ; copied from 0117
0058 r22 = r20 * #8 ; initial value of r22
005A r14 = r8 + r1 ; copied from 0320
005B r15 = r14 * #8 ; initial value of r15 (0330)
005C r49 = r2 + #1
005D r50 = r49 * #8 ; strength reduced increment
0040 G0000:
0060 cmp r1, r2 ; i < n
0070 bge G0001
0080
0118 r10 = r40 ; strength reduced expression to r40
0090 ; for (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 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0320 ; r14 = r8 + r1 killed ; dead code
0330 ; r15 = r14 * #8 killed ; strength reduced
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 r1 = r1 + #1
0385 r8 = r8 + r2 ; strength reduce r8 = r1 * r2
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0389 r15 = r15 + r50 ; strength reduce 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 ; for (i = 0, i < n; i++)
0020 {
0030 ; r1 = #0 ; i = 0, becomes dead code
0050 load r2, n
0220 fr3 = #0.0
0340 fr4 = #1.0
0055 ; r8 = #0 killed ; r8 no longer used
0056 r40 = #0 ; initial value for r8 * 8
0057 r30 = r2 * #8 ; increment for r40
0058 ; r20 = r2 killed ; r8 = 0, becomes dead code
0058 r22 = r2 * #8 ; r20 = r2
005A ; r14 = #0 killed ; r8 = 0, becomes dead code
005B r15 = #0 ; r14 = 0
005C r49 = r2 + #1
005D r50 = r49 * #8 ; strength reduced increment
005D r60 = r2 * r30 ; new limit for r40
0040 G0000:
0060 ; cmp r1, r2 killed ; i < n; induction variable replaced
0065 cmp r40, r60 ; i * 8 * n < 8 * n * n
0070 bge G0001
0080
0118 r10 = r40 ; strength reduced expression to r40
0090 ; for (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 ; strength reduced multiply
0260 br G0002
0270 }
0280 G0003:
0290 ; A[i,i] = 1.0;
0350 fstore fr4, A[r15]
0360
0370 ;i++
0380 ; r1 = r1 + #1 killed ; dead code (r40 controls loop)
0385 ; r8 = r8 + r2 killed ; dead code
0386 r40 = r40 + r30 ; strength reduce expression r8 * 8
0388 r22 = r22 + r30 ; strength reduce r22 = r20 * 8
0389 r15 = r15 + r50 ; strength reduce 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) |
Индукционная переменная (сирота)
[ редактировать ]Индукционная переменная или рекурсивное уменьшение силы заменяет функцию некоторой систематически изменяющейся переменной более простым расчетом с использованием предыдущих значений функции. В процедурном языке программирования это применимо к выражению, включающему переменную цикла, а в декларативном языке — к аргументу рекурсивной функции . Например,
f x = ... (3 ** x) ... (f (x + 1)) ...
становится
f x = f' x 1
where
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 г.