GCC ARM умножение оптимизации - PullRequest
Новая
       36

GCC ARM умножение оптимизации

0 голосов
/ 18 декабря 2018

Я читал о дизайне ALU и Алгоритм Бута , который используется для оптимизации умножения в двоичном виде.Это заставило меня задуматься о том, как компиляторы, такие как gcc, оптимизируют умножение для процессоров, где умножение не так быстро, как сдвиг битов, таких как ARM 32bit.Вот ASM, полученный при попытке умножить переменную на 0xaaa (что является худшим случаем алгоритма Бута): 

    mov     r2, r3      // r3 is an arbitrary variable
    lsl     r2, r2, #1
    add     r2, r2, r3
    lsl     r3, r2, #3
    sub     r3, r3, r2
    lsl     r2, r3, #6
    add     r3, r3, r2
    lsl     r3, r3, #1

Я не могу понять какой-либо шаблон или правило, которое сделалоследующий вывод.Я думал о том, чтобы посмотреть на исходный код gcc, но понятия не имею, где искать. Может ли кто-то пролить свет на то, что такое алгоритм и как он обобщается на любой множитель?

Ответы [ 2 ]

0 голосов
/ 18 декабря 2018

элементарное умножение, не все, что вы найдете, будет использовать какой-то алгоритм, на котором кто-то поставит свое имя.

десятичное число

33 * 12 

  33
* 12
=====
  66  ((33*2)<<0)
+33   ((33*1)<<1)
========

основание 2имеет особенность, что второй операнд может содержать либо нули, либо единицы:

0b110 * 0b101 

    110
*   101
=========   
    110     ((110*1)<<0)
   000      ((110*0)<<1)
+ 110       ((110*1)<<2)
===========

ненулевые биты - вот что важно.Таким образом, умножение на пять раз составляет

x * 5 = (x * 4) + (x * 1) = (x << 2) + x = ((x + x) << 1) + x = ((x << 1) << 1) + x </p>

x * 10 - это просто сдвиг влево еще раз.x * 10 = (x * 8) + (x * 2) = ((x + x) << 1) + x) << 1 </p>

и т. д. Вы можете играть в нее, как хотите, чтобы оптимизироватьдля целевой архитектуры.

0xAAA = (0x5 << 9) + (0x5 << 5) + (0x5 << 1) или (1 << 11) + (1 << 9) + (1<< 7) + (1 << 5) + (1 << 3) + (1 << 1) </p>

различные способы оптимизации оттуда.

0 голосов
/ 18 декабря 2018

Собранная вами сборка не является обобщенным множителем - компилятор выполнил некоторый алгоритм в автономном режиме и жестко запрограммировал константы и арифметические операции, необходимые для фиксированного вычисления f(X) = X * 0xaaa. 

mov     r2, r3      // r2 = X, r3 = X
lsl     r2, r2, #1  // r2 = 2 * X
add     r2, r2, r3  // r2 = 2X + X = 3X
lsl     r3, r2, #3  // r3 = 8 * 3X = 24X
sub     r3, r3, r2  // r3 = 24X - 3X = 21X
lsl     r2, r3, #6  // r2 = 64 * 21X = 1344X
add     r3, r3, r2  // r3 = 21X + 1344X = 1365X
lsl     r3, r3, #1  // r3 = 2 * 1365 = 2730X = 0xAAA * X

В этомв сценарии компилятору не нужно использовать алгоритм умножения общего назначения, как у Бута;он знает значение, к которому стремится, поэтому он просто предопределяет наилучший способ генерации постоянного масштабирования с помощью 0xAAA, используя сдвиги, сложения и вычитания.

Общая проблема - «Умножение одной константы»проблема - в Интернете есть статьи (оптимальные решения для произвольного числа битов - это "трудная" проблема, поэтому есть много статей для исследований).

...