Как выполнить сдвиг вправо в Y86-64 (или других игрушечных ISA с ADD + AND, но без родного сдвига вправо)

Question

Я пытаюсь выполнить сдвиг вправо на Y86-64

Чтобы сделать сдвиг влево, я знаю, что мне нужно умножить на 2 ^ n, где n - это число битовых сдвигов, которое мы хотим, например, если мы хотим сдвинуть на 4, это 2 ^ 4 = 16 и сделать цикл сложений чтобы выполнить умножение, но я не уверен, что делать для правильных сдвигов. Я думаю, что мне нужно выполнить деление, но не уверен, как подойти к этому

pcount_do:
     movq $0, %rax
.L2: movq %rdi, %rdx
     shrq %rdi
     ret

Answer 1

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

Ответ Маттео читает в переменной позиции, сдвигая маску и записывая в позициикоторый перемещается с шагом блокировки, начиная с нижней части регистра (сдвигая другую маску).

Проще прочитать MSB входа , затем сдвинуть влево ввод влево-сдвиньте вход с помощью add same,same и повторите.Таким образом, мы читаем биты, начиная с верхнего бита, и строим результат, начиная с его MSB.(Мы оставили сдвиг по 1 биту за раз в место назначения с ДОБАВЛЕНИЕМ к левому смещению и условным добавлением, чтобы установить новую позицию бита или нет.)

Мы можем использовать сравнение со знаком с добавлением 2 кчитать верхний бит в регистре. Если он установлен, x < 0, в противном случае это не так.

x86 и y86 имеют флаг SF, который устанавливается в соответствии с MSB результата (ALUоперация).x86 имеет js / cmovs / sets инструкции, которые непосредственно проверяют условие SF.У y86 есть только jl / jge и другие условия сравнения со знаком, которые проверяют SF!=OF, поэтому нам нужно сделать дополнительное сравнение от нуля до очистки OF (x - 0 не может переполниться).

Или семантически, фактически сравнивать с нулем, а не просто читать SF.(За исключением того, что мы можем оптимизировать сравнение с нулем в andl %eax,%eax или andq %rax,%rax, полезно, если вы используете версию y86, в которой нет суб-немедленной версии. В y86 также отсутствует версия x86-деструктивные test и cmp инструкции, похожие на and и sub, но только с флагами записи.)

32-битная версия y86 протестирована на https://www.simn.me/js-y86/

Портирование наy86-64 должен быть почти тривиальным.(Измените имена регистров, и 32 станет 64).
Контрольный пример: 0x12345 >> 1 = 0x000091a2.(Я не вижу способа постоянной привязки кода на этом сайте, как позволяет проводник компилятора Godbolt.)

   # constant input test case
    irmovl  0x12345, %eax
    #  irmovl  3, %ecx           # this could trivial handle variable counts, but doesn't.

# start of right-shift block:
# input: EAX = number to be shifted
# output: EDX =  number >> 1
# clobbers: EAX, ECX, EDI.   (EDI=1 to work around lack of add-immediate)

    xorl    %edx, %edx      # dst = 0.   like # irmovl  $0, %edx
    irmovl  1, %edi         # y86 is missing immediate add?

# shift 32-n bits from EAX into the bottom of EDX
# one at a time using SF to read them from the MSB
    irmovl  31, %ecx        # hard code count = 32 - 31
                            # or calculate this as 32 - count with neg / add or equivalent
rshift:                    # do {
    addl   %edx, %edx       # dst <<= 1

    andl   %eax, %eax       # compare against zero because y86 is missing js / cmovs that tests just SF
    jge   MSB_zero          # jge = jnl = not lower
    xorl    %edi,  %edx      # edx ^= 1.   y86 is missing OR?  low bit = 0 so we can ADD or XOR to set it
  MSB_zero:

    addl   %eax, %eax       # src <<= 1

    subl   %edi, %ecx
    jne   rshift            # }while(--ecx);  # semantically jnz


    halt # result in EDX
    #shr    $1, %eax

Я использовал xor-zeroing, потому что этот симулятор y86 собирается в переменную-длина машинного кода, как x86.(Так что irmovl 0, %edx будет менее эффективным).

---

Или сделайте перенос из MSB EAX в LSB EDX без ответвлений с CMOVL

# loop body:
    addl       %edx, %edx      # dst <<= 1

    xorl       %esi, %esi      # esi = 0
    sub        %esi, %eax      # src -= 0  to set flags
    cmovl      %edi, %esi      # esi = (src<0) ? 1 : 0  = MSB of EAX
    addl       %esi, %edx      # copy the bit into EDX  (can't carry to higher bits)

    addl       %eax, %eax      # src <<= 1

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

---

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

Но без смещения влево для эффективной сборки отдельных байтов вам потребуется отдельная LUT из 256 слов для каждой позиции байта!Или загрузите со смещения, а затем замаскируйте байты «мусора».

О, и вам нужно смещение вправо, чтобы извлечь байты из qword для подачи индекса массива.Если y86 может выполнять загрузку байтов, то вы можете сохранить входное целое число в памяти и перезагрузить его по 1 байту за раз.Или снова эмулируйте загрузку байтов с невыровненными загрузками ключевых слов и AND с 0x00...0FF, чтобы изолировать этот байт в нижней части регистра.

---

Фактически, мы можем использовать сохранение / перезагрузку со смещением байтов и маскированием для«эффективно» выполнить сдвиг вправо на кратное 8 бит всего за несколько инструкций.

О, чёрт, но у нас есть проблема курицы / яйца для подсчета переменных во время выполнения.Нам нужно count / 8 в качестве байтового смещения, потому что в байте 8 бит.Но счетчик мал, поэтому мы могли бы использовать для него цикл повторного вычитания.(Возможно, вы захотите AND с 0x3f или 0x1f (в зависимости от размера операнда), чтобы обернуть счет в 64 или 32, как аппаратные сдвиги x86. Это позволит избежать индексации памяти вне правильного диапазона со слишком большим количеством.)

В любом случае, вы можете расширить это для обработки счетчиков смещения вправо, не кратных 8 , округлив вверх (сдвигая слишком много битов), затемпоместите нужные биты обратно по одному за раз, как в первой части вопроса.(После невыровненной загрузки эти биты попадают в верхнюю часть регистра.)

Или, возможно, использовать метод Маттео для обхода маски, используя LUT для начальных точек.Но если мы уже выполняем перезагрузку с сохранением / выравниванием для сдвига байтов, возможно, будет полезна другая перезагрузка.Мы можем вычислить правильное смещение для этого относительно первой невыровненной перезагрузки, 4 или 8 байтов ранее, поэтому начальный MSB - это бит чуть ниже младшего бита первой загрузки.

Answer 2

Учитывая, что набор инструкций Y86 пропускает смены и деления, я бы пошел на что-то эквивалентное коду C:

uint64_t lut[] = {
    1,
    2,
    4,
    8,
    16,
    32,
    64,
    128,
    256,
    512,
    1024,
    2048,
    4096,
    8192,
    16384,
    32768,
    65536,
    131072,
    262144,
    524288,
    1048576,
    2097152,
    4194304,
    8388608,
    16777216,
    33554432,
    67108864,
    134217728,
    268435456,
    536870912,
    1073741824,
    2147483648,
    4294967296,
    8589934592,
    17179869184,
    34359738368,
    68719476736,
    137438953472,
    274877906944,
    549755813888,
    1099511627776,
    2199023255552,
    4398046511104,
    8796093022208,
    17592186044416,
    35184372088832,
    70368744177664,
    140737488355328,
    281474976710656,
    562949953421312,
    1125899906842624,
    2251799813685248,
    4503599627370496,
    9007199254740992,
    18014398509481984,
    36028797018963968,
    72057594037927936,
    144115188075855872,
    288230376151711744,
    576460752303423488,
    1152921504606846976,
    2305843009213693952,
    4611686018427387904,
    9223372036854775808};

uint64_t rshift(uint64_t source, int amount) {
    uint64_t result = 0;
    for(int i = amount; i < 64; ++i) {
        if(source & lut[i]) result |= lut[i-amount];
    }
    return result;
}

Все это можно сделать, просто добавив / sub / и / или плюс таблицу поиска.

Если мы хотим быть умнее, как подсказывает @PeterCordes, мы можем использовать справочную таблицу из 8 записей и работать с целыми байтами, но для этого требуется значительно больше учета, чем зацикливание по каждому биту.

--- обновление ---

@ PetreCordes правильно отмечает, что таблица поиска на самом деле бесполезна, так как я перебираю биты, поэтому вычисление следующей степени двух с использованием суммы тривиально:

uint64_t rshift(uint64_t source, int amount) {
    uint64_t result = 0;
    uint64_t read_bit = 1;
    uint64_t write_bit = 1;
    for(int i = 0; i < amount; ++i) read_bit = read_bit + read_bit;
    for(int i = amount; i < 64; ++i) {
        if(source & read_bit) result |= write_bit;
        read_bit = read_bit + read_bit;
        write_bit = write_bit + write_bit;
    }
    return result;
}