Снижение силы

редактировать

В компиляторе конструкции, снижение прочности является оптимизацией компилятора, где дорогостоящие операции заменяются эквивалентными, но менее дорогие операциями. Классический пример уменьшения силы преобразует «сильные» умножения внутри цикла в «более слабые» сложения - что часто происходит при адресации массивов. ( Купер, Симпсон и Вик, 1995, стр. 1)

Примеры снижения прочности включают:

замена умножения в цикле на сложение
замена возведения в степень в цикле умножением

Содержание

1 Анализ кода
2 Пример снижения прочности
- 2.1 Промежуточный код
- 2.2 Множество оптимизаций
- 2.3 Внешний контур
- 2.4 Последнее умножение
3 Прочие операции по снижению численности
4 Индукционная переменная (сирота)
5 См. Также
6 Примечания
7 ссылки

Анализ кода

Большая часть времени выполнения программы обычно тратится на небольшой участок кода (называемый активной точкой ), и этот код часто находится внутри цикла, который выполняется снова и снова.

Компилятор использует методы для идентификации циклов и распознавания характеристик значений регистров в этих циклах. Для снижения прочности компилятор интересует:

Инварианты цикла: значения, которые не изменяются в теле цикла.
Индукционные переменные: значения, которые повторяются каждый раз в цикле.

Инварианты цикла - это, по сути, константы внутри цикла, но их значение может изменяться вне цикла. Индукционные переменные изменяются на известные величины. Условия относятся к конкретному циклу. Когда циклы вложены, индукционная переменная во внешнем цикле может быть инвариантом цикла во внутреннем цикле.

Снижение силы ищет выражения, включающие инвариант цикла и индукционную переменную. Некоторые из этих выражений можно упростить. Например, умножение инварианта цикла cи переменной индукцииi

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

можно заменить последовательными более слабыми добавками

c = 7; k = 0; for (i = 0; i lt; N; i++) { y[i] = k; k = k + c; }

Пример снижения прочности

Ниже приведен пример, который сократит все циклы умножения, возникающие в результате вычислений адреса индексации массива.

Представьте себе простой цикл, который устанавливает массив в единичную матрицу.

for (i = 0; i lt; n; i++) { for (j = 0; j lt; n; j++) { A[i,j] = 0.0; } A[i,i] = 1.0; }

Промежуточный код

Компилятор будет рассматривать этот код как

0010 ; for (i = 0, i lt; n; i++) 0020 ; { 0030  r1 = #0      ; i = 0 0040 G0000: 0050  load r2, n      ; i lt; n 0060  cmp r1, r2 0070  bge G0001 0080 0090  ; for (j = 0; j lt; n; j++) 0100  ; { 0110   r3 = #0     ; j = 0 0120 G0002: 0130   load r4, n    ; j lt; 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 lt; 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 lt; 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 lt; n; j++) 0100  { 0110   r3 = #0     ; j = 0 0120 G0002: 0140   cmp r3, r2    ; j lt; 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 lt; n 0145   cmp r9, r20    ; r8 + j lt; 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 lt; 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 lt; r8 + n = r20 0147   cmp r10, r22    ; r10 = 8*(r8 + j) lt; 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 lt; 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 lt; 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 lt; n; j++) 0100  { 0120 G0002: 0147   cmp r10, r22    ; r10 = 8*(r8 + j) lt; 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 lt; 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 lt; 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 lt; n; j++) 0100  { 0120 G0002: 0147   cmp r10, r22    ; r10 = 8*(r8 + j) lt; 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:

Последнее умножение

Это оставляет два цикла только с одной операцией умножения (на 0330) во внешнем цикле и без умножений во внутреннем цикле.

0010 ; for (i = 0, i lt; 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 lt; n 0070  bge G0001 0080 0118  r10 = r40      ; strength reduced expression to r40 0090  ; for (j = 0; j lt; n; j++) 0100  { 0120 G0002: 0147   cmp r10, r22    ; r10 = 8*(r8 + j) lt; 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 каждый раз в цикле. Последнее умножение цикла в 0330 можно уменьшить, добавляя (r2 + 1) * 8 каждый раз в цикле.

0010 ; for (i = 0, i lt; 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 lt; n 0070  bge G0001 0080 0118  r10 = r40      ; strength reduced expression to r40 0090  ; for (j = 0; j lt; n; j++) 0100  { 0120 G0002: 0147   cmp r10, r22    ; r10 = 8*(r8 + j) lt; 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 lt;= i lt;n, регистр r40 перейдет в 0 lt;= r40 lt;8 * n * n.

0010 ; for (i = 0, i lt; 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 lt; n; induction variable replaced 0065  cmp r40, r60     ; i * 8 * n lt; 8 * n * n 0070  bge G0001 0080 0118  r10 = r40      ; strength reduced expression to r40 0090  ; for (j = 0; j lt; n; j++) 0100  { 0120 G0002: 0147   cmp r10, r22    ; r10 = 8*(r8 + j) lt; 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:

Прочие операции по снижению силы

Этот материал является спорным. Это лучше описать как оптимизацию глазком и назначение инструкций.

Снижение силы оператора использует математические тождества для замены медленных математических операций более быстрыми операциями. Преимущества зависят от целевого ЦП, а иногда и от окружающего кода (который может повлиять на доступность других функциональных блоков в ЦП).

замена целочисленного деления или умножения на степень двойки арифметическим или логическим сдвигом
замена целочисленного умножения на константу комбинацией сдвигов, сложений или вычитаний
замена целочисленного деления константой на умножение с использованием ограниченного диапазона машинных целых чисел. Этот метод также работает, если divisor является нецелым числом, достаточно большим, чем 1, например, √2 или π.

Исходный расчет	Расчет замены
у = х / 8	у = х gt;gt; 3
у = х * 64	у = х lt;lt; 6
у = х * 2	у = х lt;lt; 1
у = х * 15	у = (х lt;lt; 4) - х
y = x / 10 (где x имеет тип uint16_t)	y = ((uint32_t) x * (uint32_t) 0xCCCD) gt;gt; 19)
y = x / π (где x имеет тип uint16_t)	y = (((uint32_t) x * (uint32_t) 0x45F3) gt;gt; 16) + x) gt;gt; 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).

Смотрите также

Примечания

^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Продвинутая реализация проекта компилятора. Морган Кауфманн. ISBN 978-1-55860-320-2. Снижение силы.
^ В таких языках, как C и Java, целочисленное деление имеет семантику округления до нуля, тогда как битовый сдвиг всегда округляется в меньшую сторону, что требует специальной обработки отрицательных чисел. Например, в Java-3 / 2оценивается-1как, тогда как-3 gt;gt; 1оцениваетсякак-2. Таким образом, в этом случае компилятор не может оптимизировать деление на два, заменив его битовым сдвигом.
^ Гранлунд, Торбьорн; Питер Л. Монтгомери. «Деление на инвариантные целые числа с помощью умножения» (PDF).
^ Джонс, Найджел. «Деление целых чисел на константы».

Ссылки

Ахо, Альфред В. ; Сетхи, Рави ; Ульман, Джеффри Д. (1986), Компиляторы: принципы, методы и инструменты (2-е изд.), ISBN 978-0-201-10088-4
Аллен, Фрэнсис Э. ; Кок, Джон ; Кеннеди, Кен (1981), «Снижение силы оператора», в Munchnik, Steven S.; Джонс, Нил Д. (ред.), Анализ потока программ: теория и приложения, Prentice-Hall, 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 или новее.