Снижение силы - Strength reduction

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

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

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

Анализ кода

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

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

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

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

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

c = 7;за (я = 0; я < N; я++){    у[я] = c * я;}

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

c = 7;k = 0;за (я = 0; я < N; я++){    у[я] = k;    k = k + c;}

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

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

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

за (я = 0; я < п; я++){    за (j = 0; j < п; j++)    {        А[я,j] = 0.0;    }    А[я,я] = 1.0;}

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

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

0010  ; для (я = 0, я <п; я ++)0020  ; {0030      r1 = #0                        ; я = 00040  G0000:0050      нагрузка r2, п                     ; я <п0060      cmp r1, r20070      Bge G000100800090      ; для (j = 0; j 0100      ; {0110           r3   = #0                 ; j = 00120  G0002:0130           нагрузка r4, п                ; j 0140           cmp r3, r40150           bge G000301600170           ; A [i, j] = 0,0;0180           нагрузка r7, п0190           r8  = r1 * r7             ; вычислить индекс i * n + j0200           r9  = r8 + r30210           r10 = r9 * #8             ; вычислить байтовый адрес0220           fr3 = #0.00230           магазин fr3, А[r10]02400250           r3 = r3 + #1              ; j ++0260           br G00020270      ; }0280  G0003:0290      ; A [i, i] = 1,0;0300      нагрузка r12, п                    ; вычислить индекс i * n + i0310      r13 = r1 * r120320      r14 = r13 + r10330      r15 = r14 * #8                 ; вычислить байтовый адрес0340      fr4 = #1.00350      магазин fr4, А[r15]03600370      ; я ++0380      r1 = r1 + #10390      br G00000400  ; }0410  G0001:

Это выражает двумерный массив А как одномерный массив размером 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                        ; я = 00050      нагрузка r2, п0130 ; нагрузка r4, n убит; используйте r20180 ; нагрузка r7, n убит; используйте r20300 ; нагрузка r12, n убит; используйте r20220      fr3 = #0.00340      fr4 = #1.00040  G0000:0060      cmp r1, r2                     ; я <п0070      Bge G000100800190      r8  = r1 * r2                  ; вычислить индекс i * n0310 ; r13 = r1 * r2 убито; используйте r8; вычислить индекс i * n0090      ; для (j = 0; j 0100        {0110           r3   = #0                 ; j = 00120  G0002:0140           cmp r3, r2                ; j 0150           Bge G000301600170           ; A [i, j] = 0,0;0200           r9  = r8 + r3             ; вычислить индекс i * n + j0210           r10 = r9 * #8             ; вычислить байтовый адрес0230           магазин fr3, А[r10]02400250           r3 = r3 + #1              ; j ++0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1,0;0320      r14 = r8  + r1                 ; вычислить индекс i * n + i0330      r15 = r14 * #8                 ; вычислить байтовый адрес0350      магазин fr4, А[r15]03600370      ; я ++0380      r1 = r1 + #10390      br G00000400    }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 = 00115           r9   = r8                 ; новое задание0117           r20  = r8 + r2            ; новый предел0120  G0002:0140  ; cmp r3, r2 убит; j 0145           cmp r9, r20               ; r8 + j 0150           Bge G000301600170           ; A [i, j] = 0,0;0200  ; r9 = r8 + r3 убито; вычислить индекс i * n + j0210           r10 = r9 * #8             ; вычислить байтовый адрес0230           магазин fr3, А[r10]02400250  ; 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            ; начальное значение r100120  G0002:0145           cmp r9, r20               ; r8 + j 0150           Bge G000301600170           ; A [i, j] = 0,0;0210  ; r10 = r9 * # 8 убито; вычислить байтовый адрес0230           магазин fr3, А[r10]02400245           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            ; начальное значение r100119           r22  = r20 * #8           ; новый предел0120  G0002:0145  ; cmp r9, r20 убитый; r8 + j 0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           Bge G000301600170           ; A [i, j] = 0,0;0230           магазин fr3, А[r10]02400245           r10 = r10 + #8            ; сила уменьшена многократно0255  ; r9 = r9 + # 1 убито; переменная цикла0260           br G0002

Внешняя петля

Вернуться ко всей картине:

0010  ; для (я = 0, я <п; я ++)0020    {0030      r1 = #0                        ; я = 00050      нагрузка r2, п0220      fr3 = #0.00340      fr4 = #1.00040  G0000:0060      cmp r1, r2                     ; я <п0070      Bge G000100800190      r8   = r1 * r2                 ; вычислить индекс i * n0117      r20  = r8 + r2                 ; предел0118      r10  = r8 * #8                 ; начальное значение r100119      r22  = r20 * #8                ; новый предел0090      ; для (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           Bge G000301600170           ; A [i, j] = 0,0;0230           магазин fr3, А[r10]02400245           r10 = r10 + #8            ; сила уменьшена многократно0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1,0;0320      r14 = r8  + r1                 ; вычислить индекс i * n + i0330      r15 = r14 * #8                 ; вычислить байтовый адрес0350      магазин fr4, А[r15]03600370      ; я ++0380      r1 = r1 + #10390      br G00000400    }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                        ; я = 00050      нагрузка r2, п0220      fr3 = #0.00340      fr4 = #1.00055      r8  = r1 * r2                  ; установить начальное значение для r80056      r40 = r8 * #8                  ; начальное значение для r8 * 80057      r30 = r2 * #8                  ; инкремент для r400058      r20 = r8 + r2                  ; скопировано с 01170058      r22 = r20 * #8                 ; начальное значение r220040  G0000:0060      cmp r1, r2                     ; я <п0070      bge G000100800190  ; r8 = r1 * r2 убито; вычислить индекс i * n0117  ; r20 = r8 + r2 убит - мертвый код0118      r10  = r40                     ; сила уменьшила экспрессию до r400119  ; r22 = r20 * # 8 убито; сила уменьшена0090      ; для (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           bge G000301600170           ; A [i, j] = 0,0;0230           магазин fr3, А[r10]02400245           r10 = r10 + #8            ; сила уменьшена многократно0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1,0;0320      r14 = r8  + r1                 ; вычислить индекс i * n + i0330      r15 = r14 * #8                 ; вычислить байтовый адрес0350      магазин fr4, А[r15]03600370      ; я ++0380      r1  = r1 + #10385      r8  = r8 + r2                  ; снижение силы r8 = r1 * r20386      r40 = r40 + r30                ; сила уменьшить выражение r8 * 80388      r22 = r22 + r30                ; снижение прочности r22 = r20 * 80390      br G00000400    }0410  G0001:

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

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

0010  ; для (я = 0, я <п; я ++)0020    {0030      r1 = #0                        ; я = 00050      нагрузка r2, п0220      fr3 = #0.00340      fr4 = #1.00055      r8  = r1 * r2                  ; установить начальное значение для r80056      r40 = r8 * #8                  ; начальное значение для r8 * 80057      r30 = r2 * #8                  ; инкремент для r400058      r20 = r8 + r2                  ; скопировано с 01170058      r22 = r20 * #8                 ; начальное значение r220040  G0000:0060      cmp r1, r2                     ; я <п0070      Bge G000100800118      r10  = r40                     ; сила уменьшила экспрессию до r400090      ; для (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           Bge G000301600170           ; A [i, j] = 0,0;0230           магазин fr3, А[r10]02400245           r10 = r10 + #8            ; сила уменьшена многократно0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1,0;0320      r14 = r8  + r1                 ; вычислить индекс i * n + i0330      r15 = r14 * #8                 ; вычислить байтовый адрес0350      магазин fr4, А[r15]03600370      ; я ++0380      r1  = r1 + #10385      r8  = r8 + r2                  ; снижение силы r8 = r1 * r20386      r40 = r40 + r30                ; сила уменьшить выражение r8 * 80388      r22 = r22 + r30                ; снижение прочности r22 = r20 * 80390      br G00000400    }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                        ; я = 00050      нагрузка r2, п0220      fr3 = #0.00340      fr4 = #1.00055      r8  = r1 * r2                  ; установить начальное значение для r80056      r40 = r8 * #8                  ; начальное значение для r8 * 80057      r30 = r2 * #8                  ; инкремент для r400058      r20 = r8 + r2                  ; скопировано с 01170058      r22 = r20 * #8                 ; начальное значение r22005А      r14 = r8 + r1                  ; скопировано из 0320005B      r15 = r14 * #8                 ; начальное значение r15 (0330)005C      r49 = r2 + #1005D      r50 = r49 * #8                 ; сила уменьшенная прибавка0040  G0000:0060      cmp r1, r2                     ; я <п0070      Bge G000100800118      r10  = r40                     ; сила уменьшила экспрессию до r400090      ; для (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           Bge G000301600170           ; A [i, j] = 0,0;0230           магазин fr3, А[r10]02400245           r10 = r10 + #8            ; сила уменьшена многократно0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1,0;0320  ; r14 = r8 + r1 убито; мертвый код0330  ; r15 = r14 * # 8 убито; сила уменьшена0350      магазин fr4, А[r15]03600370      ; я ++0380      r1  = r1 + #10385      r8  = r8 + r2                  ; снижение силы r8 = r1 * r20386      r40 = r40 + r30                ; сила уменьшить выражение r8 * 80388      r22 = r22 + r30                ; снижение прочности r22 = r20 * 80389      r15 = r15 + r50                ; уменьшение силы r15 = r14 * 80390      br G00000400    }0410  G0001:

Впереди еще много всего. Постоянное сворачивание распознает, что r1 = 0 в преамбуле, поэтому несколько инструкций будут очищены. Регистр r8 в цикле не используется, поэтому он может исчезнуть.

Кроме того, r1 используется только для управления контуром, поэтому r1 можно заменить другой переменной индукции, такой как r40. Где я пошел 0 <= i 

0010  ; для (я = 0, я <п; я ++)0020    {0030  ; r1 = # 0; i = 0, становится мертвым кодом0050      нагрузка r2, п0220      fr3 = #0.00340      fr4 = #1.00055  ; r8 = # 0 убито; r8 больше не используется0056      r40 = #0                       ; начальное значение для r8 * 80057      r30 = r2 * #8                  ; инкремент для r400058  ; r20 = r2 убит; r8 = 0, становится мертвым кодом0058      r22 = r2  * #8                 ; r20 = r2005А  ; r14 = # 0 убито; r8 = 0, становится мертвым кодом005B      r15 =       #0                 ; r14 = 0005C      r49 = r2 + #1005D      r50 = r49 * #8                 ; сила уменьшенная прибавка005D      r60 = r2 * r30                 ; новый лимит для r400040  G0000:0060  ; cmp r1, r2 убит; я <п; индукционная переменная заменена0065      cmp r40, r60                   ; я * 8 * п <8 * п * п0070      Bge G000100800118      r10  = r40                     ; сила уменьшила экспрессию до r400090      ; для (j = 0; j 0100        {0120  G0002:0147           cmp r10, r22              ; r10 = 8 * (r8 + j) <8 * (r8 + n) = r220150           Bge G000301600170           ; A [i, j] = 0,0;0230           магазин fr3, А[r10]02400245           r10 = r10 + #8            ; сила уменьшена многократно0260           br G00020270        }0280  G0003:0290      ; A [i, i] = 1,0;0350      магазин fr4, А[r15]03600370      ; я ++0380  ; r1 = r1 + # 1 убито; мертвый код (контур управления r40)0385  ; r8 = r8 + r2 убито; мертвый код0386      r40 = r40 + r30                ; сила уменьшить выражение r8 * 80388      r22 = r22 + r30                ; снижение прочности r22 = r20 * 80389      r15 = r15 + r50                ; уменьшение силы r15 = r14 * 80390      br G00000400    }0410  G0001:

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

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

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

  • заменяя целочисленное деление или умножение на степень 2 на арифметический сдвиг или логический сдвиг[2]
  • замена целочисленного умножения на константу комбинацией сдвигов, сложений или вычитаний
  • замена целочисленного деления константой на умножение с использованием ограниченного диапазона машинных целых чисел.[3] Этот метод также работает, если divisor является нецелым числом, достаточно большим, чем 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 ' Икс 1 где   f ' Икс z = ... z ... (f ' (Икс + 1) (3 * z)) ...

Здесь модифицированная рекурсивная функция f′ принимает второй параметр z = 3 ** x, позволяя заменить дорогостоящие вычисления (3 ** x) более дешевыми (3 * z).

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

Примечания

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

Рекомендации

Статья основана на материалах, взятых из Бесплатный онлайн-словарь по вычислительной технике до 1 ноября 2008 г. и зарегистрированы в соответствии с условиями «перелицензирования» GFDL, версия 1.3 или новее.