Будут ли современные (2008/2010) заклинания Visual Studio или Visual С++ Express выдавать инструкции x86 MUL (беззнаковое умножение) в скомпилированном коде? Я не могу найти или придумать пример, где они появляются в скомпилированном коде, даже при использовании неподписанных типов.
Если VS не скомпилируется с использованием MUL, есть ли обоснование, почему?
imul (со знаком) и mul (без знака) имеют форму с одним операндом, которая имеет edx:eax = eax * src. т.е. 32x32b => 64b с полным умножением (или 64x64b => 128b).
186 добавили форму imul dest(reg), src(reg/mem), immediate, а 386 добавили форму imul r32, r/m32, каждая из которых вычисляет только нижнюю половину результата. (Согласно приложению B NASM см. также вики-тег x86)
При умножении двух 32-битных значений младшие значащие 32 бита результата одинаковы, независимо от того, считаете ли вы значения знаковыми или беззнаковыми. Другими словами, разница между умножением со знаком и без знака становится очевидной, только если вы посмотрите на "верхнюю" половину результата, которую один операнд вставляет в imul/mul в edx и два или три операнда imul никуда не денется. Таким образом, многооперандные формы imul могут использоваться для значений со знаком и без знака, и Intel не нужно было также добавлять новые формы mul. (Они могли бы сделать мульти-операнд mul синонимом для imul, но это сделало бы выходные данные дизассемблирования не соответствующими источнику.)
В C результаты арифметических операций имеют тот же тип, что и операнды (после целочисленного преобразования для узких целочисленных типов). Если вы умножите два int вместе, вы получите int, а не long long: "верхняя половина" не сохраняется. Следовательно, компилятору C требуется только то, что обеспечивает imul, и, поскольку imul проще в использовании, чем mul, компилятор C использует imul, чтобы избежать необходимости инструкций mov для ввода данных в/из eax ].
В качестве второго шага, поскольку компиляторы C часто используют многооперандную форму imul, Intel и AMD прилагают усилия для того, чтобы сделать это как можно быстрее. Он записывает только один выходной регистр, а не e/rdx:e/rax, поэтому процессоры могли оптимизировать его проще, чем форма с одним операндом. Это делает imul еще более привлекательным.
Форма с одним операндом mul/imul полезна при реализации арифметики большого числа. В C в 32-битном режиме вы должны получить несколько вызовов mul путем умножения значений unsigned long long вместе. Но, в зависимости от компилятора и ОС, эти коды операций mul могут быть скрыты в какой-то отдельной функции, поэтому вы не обязательно их увидите. В 64-битном режиме long long имеет только 64 бита, а не 128, и компилятор просто использует imul.
Существует три разных типа умножения инструкций на x86. Первый - MUL reg, который без знака умножает EAX на reg и помещает (64-разрядный) результат в EDX:EAX. Второй - IMUL reg, что делает то же самое с подписанным умножением. Третий тип - это IMUL reg1, reg2 (умножает reg1 на reg2 и сохраняет 32-битный результат в reg1) или IMUL reg1, reg2, imm (умножает reg2 на imm и сохраняет 32-битный результат в reg1).
Так как в C умножение двух 32-битных значений приводит к 32-битным результатам, компиляторы обычно используют третий тип (подпись не имеет значения, младшие 32 бита согласуются между множителями, подписанными и unsigned 32x32). VС++ будет генерировать "длинные многократные" версии MUL/IMUL, если вы действительно используете полные 64-битные результаты, например. здесь:
unsigned long long prod(unsigned int a, unsigned int b)
{
return (unsigned long long) a * b;
}
2-операндовые (и 3-операндные) версии IMUL быстрее, чем версии с одним операндом, просто потому, что они не дают полного 64-битного результата. Широкие мультипликаторы большие и медленные; гораздо проще построить меньший множитель и синтезировать длинные множители, используя, при необходимости, Microcode. Кроме того, MUL/IMUL записывает два регистра, которые, как правило, обычно разрешаются путем разбиения на несколько инструкций внутри системы - гораздо проще для переопределения аппаратного обеспечения для отслеживания двух зависимых инструкций, каждый из которых записывает один регистр (большинство команд x86 выглядят так, как внутри), чем отслеживать одну инструкцию, которая записывает два.
Согласно http://gmplib.org/~tege/x86-timing.pdf, команда IMUL имеет более низкую задержку и более высокую пропускную способность (если я правильно читаю таблицу), Возможно, VS просто использует более быструю инструкцию (предполагая, что IMUL и MUL всегда производят один и тот же вывод).
У меня нет Visual Studio, поэтому я попытался получить что-то еще с GCC. Я также всегда получаю некоторые изменения IMUL.
Это:
unsigned int func(unsigned int a, unsigned int b)
{
return a * b;
}
Соответствует этому (с -O2):
_func:
LFB2:
pushq %rbp
LCFI0:
movq %rsp, %rbp
LCFI1:
movl %esi, %eax
imull %edi, %eax
movzbl %al, %eax
leave
ret
Моя интуиция подсказывает мне, что компилятор выбрал IMUL произвольно (или в зависимости от того, что было быстрее из двух), так как биты будут одинаковыми, если он использует unsigned MUL или подписанный IMUL. Любое 32-битное целочисленное умножение будет 64-битным, охватывающим два регистра, EDX:EAX. Переполнение происходит в EDX, который по существу игнорируется, поскольку мы заботимся только о 32-битном результате в EAX. Используя IMUL, при необходимости добавьте в EDX, но опять же, нам все равно, поскольку нас интересует только 32-разрядный результат.
Сразу после того, как я посмотрел на этот вопрос, я обнаружил MULQ в моем сгенерированном коде при делении.
Полный код превращает большое двоичное число в куски миллиарда, чтобы его можно было легко преобразовать в строку.
Код С++:
for_each(TempVec.rbegin(), TempVec.rend(), [&](Short & Num){
Remainder <<= 32;
Remainder += Num;
Num = Remainder / 1000000000;
Remainder %= 1000000000;//equivalent to Remainder %= DecimalConvert
});
Оптимизированная сгенерированная сборка
00007FF7715B18E8 lea r9,[rsi-4]
00007FF7715B18EC mov r13,12E0BE826D694B2Fh
00007FF7715B18F6 nop word ptr [rax+rax]
00007FF7715B1900 shl r8,20h
00007FF7715B1904 mov eax,dword ptr [r9]
00007FF7715B1907 add r8,rax
00007FF7715B190A mov rax,r13
00007FF7715B190D mul rax,r8
00007FF7715B1910 mov rcx,r8
00007FF7715B1913 sub rcx,rdx
00007FF7715B1916 shr rcx,1
00007FF7715B1919 add rcx,rdx
00007FF7715B191C shr rcx,1Dh
00007FF7715B1920 imul rax,rcx,3B9ACA00h
00007FF7715B1927 sub r8,rax
00007FF7715B192A mov dword ptr [r9],ecx
00007FF7715B192D lea r9,[r9-4]
00007FF7715B1931 lea rax,[r9+4]
00007FF7715B1935 cmp rax,r14
00007FF7715B1938 jne NumToString+0D0h (07FF7715B1900h)
Обратите внимание на инструкцию MUL 5 строк. Этот сгенерированный код чрезвычайно неинтуитивный, я знаю, на самом деле он не похож на скомпилированный код, но DIV чрезвычайно медленный ~ 25 циклов для 32-битного div и ~ 75 в соответствии с этим диаграмма на современных ПК по сравнению с MUL или IMUL (около 3 или 4 циклов), и поэтому имеет смысл попытаться избавиться от DIV, даже если вам нужно добавить всевозможные дополнительные инструкции.
Я не полностью понимаю оптимизацию здесь, но если вы хотите увидеть рациональное и математическое объяснение использования времени компиляции и умножения для деления констант, см. этот бумага.
Это пример того, как компилятор использует производительность и возможности полного 64-битного неиспользуемого умножения, не показывая С++-кодер никаких признаков этого.
Как уже объяснялось, C/С++ не выполняет операции word*word to double-word, для которых лучше всего подходит команда mul. Но есть случаи, когда вы хотите word*word to double-word, поэтому вам нужно расширение для C/С++.
GCC, Clang и ICC предоставляют встроенный тип __int128, который вы можете использовать для косвенного получения инструкции mul.
В MSVC он обеспечивает _ umul128 собственный (по крайней мере, VS 2010), который генерирует инструкцию mul. С этим встроенным наряду с _ addcarry_u64 можно было создать собственный эффективный тип __int128 с MSVC.