Если вы умножаете два значения, которые вы не знаете заранее, фактически невозможно выполнить инструкцию умножения в ассемблере x86.
Если вы заранее знаете значение одного из операндов,Вы можете быть в состоянии превзойти инструкцию умножения, используя небольшое количество добавлений.Это особенно хорошо работает, когда известный операнд мал и имеет только несколько битов в двоичном представлении.Чтобы умножить неизвестное значение x на известное значение, состоящее из 2 ^ p + 2 ^ q + ... 2 ^ r, вы просто добавляете x * 2 ^ p + x * 2 ^ q + .. x * 2 * r, если биты p, q, ... и r установлены.Это легко сделать в ассемблере, сдвинув влево и добавив:
; x in EDX
; product to EAX
xor eax,eax
shl edx,r ; x*2^r
add eax,edx
shl edx,q-r ; x*2^q
add eax,edx
shl edx,p-q ; x*2^p
add eax,edx
Ключевая проблема с этим заключается в том, что для этого требуется по крайней мере 4 такта, предполагая суперскалярный ЦП, ограниченный зависимостями регистров.Умножение обычно занимает 10 или меньше тактов на современных процессорах, и если эта последовательность удлиняется по времени, вы могли бы также сделать умножение.
Чтобы умножить на 9:
mov eax,edx ; same effect as xor eax,eax/shl edx 1/add eax,edx
shl edx,3 ; x*2^3
add eax,edx
Этоудары умножаются;должно занимать только 2 такта.
Менее известно, что используется команда LEA (эффективный адрес загрузки) для быстрого умножения на маленькую постоянную.LEA, который в худшем случае занимает только один такт, его время выполнения часто может перекрываться с другими инструкциями суперскалярными ЦП.
LEA, по сути, «добавляет два значения с небольшими постоянными множителями».Он вычисляет t = 2 ^ k * x + y для k = 1,2,3 (см. Справочное руководство Intel) для t, x и y - любой регистр.Если x == y, вы можете получить 1,2,3,4,5,8,9 раз x, но использование x и y в качестве отдельных регистров позволяет объединять промежуточные результаты и , перемещаемые в другиерегистры (например, к т), и это оказывается очень удобно.Используя его, вы можете выполнить умножение на 9 с помощью одной инструкции:
lea eax,[edx*8+edx] ; takes 1 clock
Тщательно используя LEA, вы можете умножить на множество своеобразных констант за небольшое количество циклов:
lea eax,[edx*4+edx] ; 5 * edx
lea eax,[eax*2+edx] ; 11 * edx
lea eax,[eax*4] ; 44 * edx
Чтобы сделать это, вы должны разложить ваш постоянный множитель на различные факторы / суммы, включающие 1,2,3,4,5,8 и 9. Удивительно, сколько маленьких констант вы можете сделать это, и до сих пор толькоиспользуйте 3-4 инструкции.
Если вы разрешаете использовать другие обычно одночасовые инструкции (например, SHL / SUB / NEG / MOV), вы можете умножить на некоторые постоянные значения, которые чистый LEA не может сделать так эффективносамо собой.Умножить на 31:
lea eax,[4*edx]
lea eax,[8*eax] ; 32*edx
sub eax,edx; 31*edx ; 3 clocks
Соответствующая последовательность LEA длиннее:
lea eax,[edx*4+edx]
lea eax,[edx*2+eax] ; eax*7
lea eax,[eax*2+edx] ; eax*15
lea eax,[eax*2+edx] ; eax*31 ; 4 clocks
Выяснить эти последовательности немного сложно, но вы можете организовать организованную атаку.
Поскольку LEA, SHL, SUB, NEG, MOV - это наихудший случай однократных команд и нулевые часы, если они не зависят от других команд, вы можете рассчитать стоимость выполнения любой такой последовательности.Это означает, что вы можете реализовать алгоритм динамического программирования для генерации наилучшей возможной последовательности таких инструкций.Это полезно только в том случае, если счетчик тактов меньше целочисленного умножения для вашего конкретного процессора (я использую 5 часов в качестве практического примера), и , он не использует все регистры или, по крайней мере, егоне использует регистры, которые уже заняты (избегая разливов).
Я на самом деле встроил это в наш PARLANSE компилятор, и это очень эффективно для вычисления смещений в массивахструктуры A [i], где размер структурного элемента в A - известная постоянная.Умный человек, возможно, кеширует ответ, поэтому его не нужно пересчитывать каждый раз, когда происходит умножение одной и той же константы;На самом деле я этого не делал, потому что время генерации таких последовательностей меньше, чем вы ожидаете.
Мягко интересно распечатать последовательности инструкций, необходимые для умножения на все константы от 1 до 10000.Большинство из них можно сделать в 5-6 инструкциях в худшем случае.Как следствие, компилятор PARLANSE вряд ли когда-либо использует фактическое умножение при индексации даже самых неприятных массивов вложенных структур.