x86 MUL Инструкция от VS 2008/2010

Question

Будут ли современные (2008/2010) заклинания Visual Studio или Visual C ++ Express создавать инструкции MUL x86 (без знака умножения) в скомпилированном коде? Я не могу найти или придумать пример, где они появляются в скомпилированном коде, даже при использовании неподписанных типов.

Если VS не компилируется с использованием MUL, есть ли объяснение, почему?

Answer 1

imul (со знаком) и mul (без знака) имеют форму с одним операндом, которая имеет значение edx:eax = eax * src.т.е. 32x32b => 64b полное умножение (или 64x64b => 128b).

286 добавили форму imul dest(reg), src(reg/mem), immediate, а 386 добавили форму imul r32, r/m32, обе из которых тольковычислить нижнюю половину результата.(Ссылка из вики-тега 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.

Answer 2

На 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 бита согласуются между умножениями со знаком и без знака 32x32). VC ++ сгенерирует «длинное умножение» версий MUL / IMUL, если вы действительно используете полные 64-битные результаты, например, здесь:

unsigned long long prod(unsigned int a, unsigned int b)
{
  return (unsigned long long) a * b;
}

2-операндные (и 3-операндные) версии IMUL работают быстрее, чем однооперандные версии просто потому, что они не дают полного 64-битного результата. Широкие множители большие и медленные; гораздо проще создать меньший множитель и синтезировать длинные умножения, используя микрокод, если это необходимо. Кроме того, MUL / IMUL записывает два регистра, которые снова обычно разрешаются путем внутреннего разбиения его на несколько инструкций - аппаратному устройству переупорядочения намного проще отслеживать две зависимые инструкции, каждая из которых записывает один регистр (большинство инструкций x86 выглядят внутренне так ) чем отслеживать одну инструкцию, которая записывает две.

Answer 3

Согласно http://gmplib.org/~tege/x86-timing.pdf, инструкция IMUL имеет меньшую задержку и более высокую пропускную способность (если я правильно читаю таблицу).Возможно, VS просто использует более быструю инструкцию (при условии, что IMUL и MUL всегда выдают один и тот же вывод).

У меня нет под рукой Visual Studio, поэтому я попытался получить что-то еще с помощью GCC.Я также всегда получаю некоторые варианты IMUL.

This:

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

Answer 4

Сразу после того, как я посмотрел на этот вопрос, я обнаружил MULQ в сгенерированном коде при делении.

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

C ++ код:

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-разрядного деления и ~ 75 согласно этому графику на современных ПК по сравнению с MUL или IMUL (около 3 или 4 циклов), поэтому имеет смысл попытаться избавиться от DIV, даже если вам нужно добавить всевозможные дополнительные инструкции.

Я не совсем понимаю оптимизацию здесь, но если вы хотите увидеть рациональное и математическое объяснение использования времени компиляции и умножения для разделения констант, см. Эту статью .

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

Answer 5

Моя интуиция подсказывает мне, что компилятор выбрал IMUL произвольно (или в зависимости от того, что было быстрее двух), поскольку биты будут одинаковыми, независимо от того, использует он беззнаковый MUL или подписанный IMUL.Любое 32-разрядное целочисленное умножение будет 64-разрядным, охватывающим два регистра, EDX:EAX.Переполнение переходит в EDX, что по существу игнорируется, поскольку мы заботимся только о 32-битном результате в EAX.Использование IMUL будет расширять знак до EDX по мере необходимости, но, опять же, нам все равно, потому что нас интересует только 32-битный результат.

Answer 6

Как уже объяснялось, C / C ++ не выполняет word*word to double-word операций, для которых лучше всего подойдет инструкция mul. Но есть случаи, когда вы хотите word*word to double-word, поэтому вам нужно расширение до C / C ++.

GCC, Clang и ICC предоставляют встроенный тип __int128, который можно использовать для косвенного получения инструкции mul.

В MSVC он обеспечивает _umul128 встроенную функцию (начиная с версии 2010), которая генерирует инструкцию mul. С этим свойством вместе со свойством _addcarry_u64 вы можете создать свой собственный эффективный тип __int128 с MSVC.