Что делает __modti3? - PullRequest
Новая
       13

Что делает __modti3?

0 голосов
/ 18 сентября 2018

Недавно я попытался написать программу для вычисления (a * b)% m, где (0 <= a, b, m <= 2 ^ 63-1).И, к счастью, я знаю, что GCC поддерживает <code>__int128_t.В итоге я получаю следующую программу: 

#include <stdint.h>

int64_t multimod(int64_t a, int64_t b, int64_t m)
{
  __int128_t ab = (__int128_t)a * b;
  ab %= m;
  return ab;
}

Но я хочу сделать это без __int128_t, чтобы испытать себя и сделать эту функцию более эффективной.Я решил сделать это, сначала смоделировав процесс программы сборки этой функции.Поэтому я использовал objdump и получил следующую часть multimod. 

int64_t multimod(int64_t a, int64_t b, int64_t m)
{
 720:   55                      push   %rbp
 721:   49 89 d1                mov    %rdx,%r9 
 724:   49 89 f8                mov    %rdi,%r8
 727:   49 c1 f8 3f             sar    $0x3f,%r8
 72b:   48 89 f0                mov    %rsi,%rax
 72e:   48 c1 f8 3f             sar    $0x3f,%rax
 732:   4c 89 c2                mov    %r8,%rdx
 735:   48 0f af d6             imul   %rsi,%rdx
 739:   48 0f af c7             imul   %rdi,%rax
 73d:   49 89 c0                mov    %rax,%r8 
 740:   49 01 d0                add    %rdx,%r8 
 743:   48 89 f8                mov    %rdi,%rax
 746:   48 f7 e6                mul    %rsi
 749:   48 89 c7                mov    %rax,%rdi
 74c:   49 8d 34 10             lea    (%r8,%rdx,1),%rsi
 750:   4c 89 c9                mov    %r9,%rcx
 753:   48 c1 f9 3f             sar    $0x3f,%rcx
 757:   4c 89 ca                mov    %r9,%rdx
 75a:   e8 61 00 00 00          callq  7c0 <__modti3>
 75f:   5d                      pop    %rbp
 760:   c3                      retq

Я проанализировал всю часть и считаю, что ее можно разделить на две части --- 1. получить правильное 128-Битовое произведение 64-битной переменной a и b 2. __modti3.

I STFW и узнал, что прототипом __modti3 является long long __modti3(long long a, long long b).Но ассемблерный код не получает это таким образом.Когда он вызывает __modti3, первый аргумент %rdi содержит младший 64-битный продукт a и b, второй аргумент %rsi содержит hign 64-битного продукта a и bтретий аргумент %rdx, содержащий m.Так что же __modti3 сделал, чтобы получить правильный ответ?

1 Ответ

0 голосов
/ 18 сентября 2018

Нет, long long является 64-битным.Вы можете видеть, что gcc передает аргументы __modti3 в rdi, rsi, rdx и rcx.(т.е. первые 4 слота прохождения аргументов в ABI SysV x86-64.)

Таким образом, это два 128-битных операнда, передаваемых по значению в парах регистров: rsi:rdi и rcx:rdx.

Это на самом деле __int128 __modti3(__int128 quotient, __int128 divisor); В этом весь смысл и причина существования: x86-64 имеет long long % long long остаток на оборудовании с
idiv r64, который gcc будет использовать для переменной времени выполненияделители / модули.

Обратите внимание, что ваша функция расширяет знак m из rdx в rcx:rdx с 

mov    %r9, %rcx        # originally from RDX on entry; you didn't enable full optimization
sar    $63, %rcx        # copy sign bit to all bit positions.

Это точно так же, как cqo(AT & T cqto) делает для расширения RAX в RDX: RAX.

Кстати, код легче читать, если включить полную оптимизацию с помощью -O3.Тогда вы получите только 1 инструкцию умножения, используя 64-битные входы и производя 128-битный выход.https://gcc.godbolt.org/z/0gKc5d

Компиляция с -O1 или -Og иногда более полезна, если вы хотите, чтобы asm больше походил на исходный код, но так как C не имеет оператора умножения с расширением, вы нена самом деле хочу этого.Вы хотите , чтобы компилятор оптимизировал расширение входов перед умножением на умножение с расширением вместо того, чтобы расширять входы в пары регистров и выполнять умножение 128x128 => 128-бит.(Что происходит в коде, который вы показываете.)

...