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

Question

У меня есть небольшое теоретическое любопытство. Оператор == в C возвращает 1 в случае положительного равенства, 0 в противном случае. Мои знания по сборке очень ограничены. Однако мне было интересно, возможно ли теоретически реализовать новый оператор, который возвращает ~0 в случае положительного равенства, 0 в противном случае - но при одном условии: он должен выдавать такое же количество инструкций по сборке как оператор == . Это на самом деле просто теоретическое любопытство, я не имею в виду практического использования.

EDIT

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

ВТОРОЕ РЕДАКТИРОВАНИЕ

Как указал Sneftel , ничто не похоже на инструкции SETcc [ 1 ] - но способен преобразовывать биты регистра флага в значения 0 / ~0 ( вместо классического 0 / 1) - существует. Таким образом, ответ на мой вопрос, кажется, нет.

ТРЕТЬЕ РЕДАКТИРОВАНИЕ

Небольшая заметка. Я не пытаюсь представить логическое true как ~0, я пытаюсь понять, может ли логическое истина также быть , необязательно , представленное как ~0 при необходимости, без дальнейших усилий , на языке, который обычно обычно представляет true как 1. И для этого я предположил новый оператор, который «возвращает» чисел , а не логические значения (естественное логическое true «возвращено» == остается представленным как 1) - иначе я бы спросил может ли == быть перепроектирован так, чтобы «возвращать» ~0 вместо 1. Вы можете думать об этом новом операторе как о половинной принадлежности к семейству битовых операторов, которые «возвращают» числа, а не логические значения (и под логическими значениями я не подразумеваю логические типы данных, я имею в виду что-либо вне пары чисел 0 / 1, то есть то, что логическое значение предназначено в C в результате логической операции).

Я знаю, что все это может показаться бесполезным, но я предупреждал: это теоретический вопрос.

Однако здесь мой вопрос, похоже, решен явно:

Некоторые языки представляют логический язык как целое число со всеми установленными битами. Это представление можно получить, выбрав логически противоположное условие для инструкции SETcc, затем уменьшив результат. Например, чтобы проверить наличие переполнения, используйте инструкцию SETNO, затем уменьшите результат.

Так что, похоже, прямой инструкции нет, поскольку использование SETNE и затем уменьшение означает добавление еще одной инструкции.

Answer 1

РЕДАКТИРОВАТЬ: как указывают другие люди, есть некоторые разновидности "условно назначить 0/1" там. Вид подрывает мою точку зрения :) По-видимому, логический тип 0/1 допускает более глубокую оптимизацию, чем логический 0 / ~ 0.

---

Понятие "оператор возвращает значение" является высокоуровневым, оно не сохраняется до уровня сборки. Эта 1/0 может существовать только как бит в регистре флагов, или даже не так.

Другими словами, присвоение определенного C-значения оператора равенства переменной размером int не является примитивом на уровне сборки. Если вы напишите x = (a == b), компилятор может реализовать его как

cmp a, b ; set the Z flag
cmovz x, 1 ; if equals, assign 1
cmovnz x, 0 ; if not equals, assign 0

Или это можно сделать с помощью условных переходов. Как вы можете видеть, присвоение ~ 0 в качестве значения для ИСТИНЫ потребует тех же команд, только с другим операндом.

Ни одна из архитектур, с которыми я знаком, не реализует сравнение на равенство как "присваивает 1 или 0 регистру общего назначения".

Answer 2

Не существует ассемблерной реализации оператора C.Например, нет инструкции x86, которая сравнивает два аргумента и приводит к 0 или 1, только одна, которая сравнивает два аргумента и помещает результат в бит в регистр флага.И это обычно не происходит, когда вы используете ==.

Пример:

void foo(int a, int b) {
    if(a == b) { blah(); }
}

производит более или менее следующую сборку:

foo(int, int):
        cmp     %edi, %esi
        je      .L12
        rep  ret
.L12:
        jmp     blah()

Обратите внимание, чтоничего там не включает в себя значение 0/1.Если вы хотите этого, вы должны действительно спросить об этом:

int bar(int a, int b) {
    return a == b;
}

, который становится:

bar(int, int):
        xor     %eax, %eax
        cmp     %edi, %esi
        sete    %al
        ret

Я подозреваю, что наличие SETcc инструкций и стало причиной вашего вопроса,так как они преобразуют биты регистра флага в значения 0/1.Нет соответствующей инструкции, которая преобразует их в 0 / ~ 0: вместо этого GCC делает умный маленький DEC, чтобы отобразить их.Но в целом результат == существует только как абстрактное и определяемое оптимизатором различие в состоянии машины между ними.

Кстати, я бы совсем не удивился, если бы некоторые реализации x86 решили объединить SETcc и следующие DEC в одну микрооперацию;Я знаю, что это делается с другими общими парами команд.Не существует простой связи между потоком инструкций и количеством циклов.

Answer 3

Сравнение векторов SIMD do дает векторы с результатами 0 / -1. Это относится к x86 MMX / SSE / AVX, ARM NEON, PowerPC Altivec и т. Д. (Они2 машины дополнения, поэтому мне нравится писать -1 вместо ~0 для представления элементов, состоящих из всех нулей / всех единичных битов.

например, pcmpeqd xmm0, xmm1заменяет каждый элемент xmm0 на xmm0[i] == xmm1[i] ? -1 : 0;

---

Это позволяет использовать их в качестве масок AND , поскольку SIMD-код не может ветвиться отдельно на каждом элементе вектора без распаковки вскаляр и обратно.Это должно быть без ответвлений. Как использовать, если условие во встроенных функциях

например, чтобы смешать 2 вектора на основе условия, без SSE4.1 pblendvb / blendvps, вы бы сравнили, а затем AND / ANDNOT/ ИЛИ ЖЕ.например, от Заменить байт другим

    __m128i mask = _mm_cmpeq_epi8(inp, val);     // movdqa xmm1, xmm0 / PCMPEQB xmm1, xmm2

    // zero elements in the original where there was a match (that we want to replace)
    inp = _mm_andnot_si128(mask, inp);   // inp &= ~mask;  // PANDN xmm0, xmm1

    //  zero elements where we keep the original
    __m128i tmp = _mm_and_si128(newvals, mask);   // newvals & mask; // PAND xmm3, xmm1

    inp = _mm_or_si128(inp, tmp);             // POR xmm0, xmm1

Но если вы хотите посчитать совпадения, вы можете вычесть результат сравнения. total -= -1 избегает необходимостиотрицать элементы вектора. Как посчитать вхождения символов, используя SIMD

Или для условного добавления чего-либо, вместо фактического смешивания, просто выполните total += (x & mask), потому что 0 является элементом идентификации для таких операций, как ADD (инекоторые другие, такие как XOR и OR).

См. Как получить доступ к массиву символов и изменить строчные буквы в верхний регистр, и наоборот и Преобразование строки в C ++ в верхнийСлучай для примеров в C с внутренними компонентами и ассемблером x86.

---

Все это не имеет отношения к ничего с операторами C и неявным преобразованием из логического значения в целое.

В C и C ++ операторы возвращают логическое условие true / false, которое в asm для большинства машин для скалярного кода (не автоматически векторизованного) отображается в бит в регистре флагов.

Преобразование этого числа в регистр - это совершенно отдельная вещь.

---

Но забавный факт: MIPS не имеет регистра флагов : он имеет некоторое сравнение -и ветвь инструкции для простогоТакие условия, как reg == reg или reg != reg (beq и bne).И ветвь на меньше нуля (ветвь на знаковом бите одного регистра): bltz $reg, target.

(И архитектурный регистр $zero, который всегда читается как ноль, так что вы можете использовать эту ветвь реализацииесли reg! = 0 или reg == 0).

Для более сложных условий для сравнения используйте slt (установлен на меньше чем) или sltu (установлен на меньше чем без знака)в регистр целых чисел.Как slt $t4, $t1, $t0 реализует t4 = t1 < t0, производя 0 или 1. Затем вы можете переходить на это значение, равное 0 или нет, или комбинировать несколько условий с логическим И / ИЛИ, прежде чем переходить на это.Если один из ваших входных данных является действительным bool, который уже равен 0 или 1, его можно оптимизировать в этом без slt.

Неполный список инструкций классических инструкций MIPS (не включая псевдоинструкции, такие как blt)которые собираются в slt в $at + bne: http://www.mrc.uidaho.edu/mrc/people/jff/digital/MIPSir.html

Но MIPS32r6 / MIPS64r6 изменил это: инструкции, генерирующие значения истинности, теперь генерируют все нули или все единицы вместо просто очистки /установка 0-битового , в соответствии с https://en.wikipedia.org/wiki/MIPS_architecture#MIPS32/MIPS64_Release_6. MIPS32 / 64 r6 не двоично совместима с предыдущими ISA MIPS, она также переставила некоторые коды операций. И из-за этого изменения, даже не совместимы с источником asm! Но этоопределенное изменение к лучшему.

---

Интересный факт, есть недокументированная инструкция SALC 8086 (установите AL из переноса) , которая по-прежнему поддерживается в 16/32-битном режиме современнымиПроцессоры Intel (и AMD?).

Это в основном похоже на sbb al,al без установки флагов: AL = CF? -1: 0. http://os2museum.com/wp/undocumented-8086-opcodes.

Вычитать с заимствованием с помощью saМой ввод дважды делает x-x - CF на x86, где CF является заимствованием для вычитания.И x-x конечно всегда ноль.(На некоторых других ISA, таких как ARM, значение флага переноса противоположно для вычитания, C set означает «без заимствования».)

В общем, вы можете сделать sbb edx,edx (или любой другой регистр, который хотите), чтобы преобразовать CF в целое число 0 / -1. Но это работает только для CF; Флаг переноса является особенным, и нет ничего эквивалентного другим флагам.

Некоторые процессоры AMD даже распознают sbb same,same как независимое от старого значения регистра, зависящее только от CF, например, обнуление xor. На других процессорах это все еще имеет тот же архитектурный эффект, но с микроархитектурной ложной зависимостью от старого значения EDX.

Answer 4

Всего за 1 дополнительный цикл вы можете просто отменить / output /.

Внутри 8086 операции сравнения существуют только во флагах. Получение значения флагов в переменную требует дополнительного кода. В значительной степени это один и тот же код, хотите ли вы, чтобы true было 1 или -1. Обычно компилятор фактически не генерирует значение 0 или 1 при оценке оператора if, но использует инструкции Jcc непосредственно для флагов, сгенерированных операциями сравнения. https://pdos.csail.mit.edu/6.828/2006/readings/i386/Jcc.htm

С 80386 был добавлен SETcc, который только устанавливает 0 или 1 в качестве ответа, так что это предпочтительное расположение, если код настаивает на сохранении ответа. https://pdos.csail.mit.edu/6.828/2006/readings/i386/SETcc.htm

И есть много новых инструкций сравнения, которые сохраняют результаты в будущих регистрах. Эти флаги считаются узким местом для остановок конвейера инструкций в современных процессорах, и во многом они не приветствуются оптимизацией кода.

Конечно, есть множество хитростей, которые вы можете сделать, чтобы получить 0, 1 или -1 для конкретного набора значений для сравнения. Нет необходимости говорить, что компилятор был оптимизирован для генерации 1 для true при применении этих трюков, и, где это возможно, он вообще не хранит значение, а просто реорганизует ваш код, чтобы избежать его.