Представьте себе два типа булевых пар в одном языке без лишних слов
У меня просто небольшое теоретическое любопытство. Оператор == в C возвращает 1 в случае положительного равенства, 0 в противном случае. Мои познания в ассемблере очень ограничены. Однако мне было интересно, возможно ли теоретически реализовать новый оператор, который возвращает ~0 в случае положительного равенства, 0 в противном случае — но при одном условии: он должен производить то же количество инструкций по сборке, что и оператор ==. На самом деле это просто теоретическое любопытство, я не имею в виду практического применения.
РЕДАКТИРОВАТЬ
Мой вопрос нацелен на процессоры x86, однако мне очень любопытно узнать, есть ли архитектуры, которые изначально делают это.
ВТОРОЕ РЕДАКТИРОВАНИЕ
Как указал Снефтел, не существует ничего похожего на инструкции SETcc [1], но способные преобразовывать биты флагового регистра в значения 0/~0 (вместо классических 0/1). Так что ответ на мой вопрос, похоже, нет.
ТРЕТЬЕ РЕДАКТИРОВАНИЕ
Небольшое примечание. Я не пытаюсь представить логическое true как ~0, я пытаюсь понять, может ли логическое истинное также быть по выбору представленным как ~0, когда это необходимо, без дальнейших усилий, в языке, который уже обычно представляет true как 1. И для этого я выдвинул гипотезу о новом операторе, который «возвращает» числа, а не логические значения (естественный логический true, «возвращаемый» ==, остается представленным как 1) — в противном случае я бы спросил, можно ли перепроектировать == для «возвращения» ~0 вместо 1. Вы можете думать об этом новом операторе как о наполовину принадлежащем семейству побитовых операторов, которые «возвращают» числа, а не логические значения (и под логическими значениями я не подразумеваю логические типы данных, я имею в виду все, что находится за пределами числовой пары 0/1 , что и подразумевается под булевым значением в C как результат логической операции).
Я знаю, что все это может показаться бесполезным, но я предупреждал: это теоретический вопрос.
Однако здесь мой вопрос, кажется, адресован явно:
Some languages represent a logical one as an integer with all bits set. This representation can be obtained by choosing the logically opposite condition for the
SETccinstruction, then decrementing the result. For example, to test for overflow, use theSETNOinstruction, then decrement the result.
Таким образом, кажется, что прямой инструкции нет, поскольку использование SETNE с последующим уменьшением означает добавление еще одной инструкции.
VBA в значительной степени делает это (когда для сравнения используется =). Это оценивается как «Истина», что равно -1.
Возможно ли это, вероятно, зависит от конкретной архитектуры, на которую вы ориентируетесь. Вы не указали это.
Теоретическая архитектура может иметь одну инструкцию сборки под управлением Windows.
@ЕвгенийШ. Я предполагаю, что такая архитектура будет разработана Microhard.
@ChristianGibbons — это должно быть macrohard, та же компания, о которой упоминается в игре Lucas Arts Sam & Max Hit The Road.
@Bathsheba Я говорю о сборке реализации теоретического нового оператора, а не о VBA.
Ваше редактирование имеет мало смысла без контекста. Ассемблерный код, сгенерированный оператором ==, очень зависит от того, что еще он делает. Он может куда-то прыгнуть, может что-то присвоить или вызвать функцию. Или даже проигнорировали и оптимизировали.
@rcgldr Я хотел поиграть только с заменой soft на hard, так как это все еще Windows, но в аппаратном, а не в программном обеспечении. Но Macrohard, безусловно, хороший выбор для пародийного имени. Кроме того, я всегда ценю олдскульные «укажи и щелкни». Это просто напомнило "Droids B Us" из Space Quest. Я не могу вспомнить, были ли у них проблемы с законом, поскольку права на термин «Дроид» принадлежали Lucasfilm.
Отметьте архитектуру. В большинстве архитектур оператор равенства, используемый для ветвления, создает инструкции, отличные от тех, которые используются в качестве выражения. В последнем случае количество инструкций зависит от компилятора, поэтому ваш вопрос превращается в: «Можем ли мы выразить оба оператора с одинаковым количеством инструкций?» Да, конечно, со временем вы удлиняете самую короткую.
@ЕвгенийШ. Я знаю. Но представьте самый простой случай, представьте себе return var_a == var_b; (не оптимизированный, конечно).
Помимо операторов C, сравнения в SSE (возможно, часть x86) действительно приводят к 0 или ~ 0 в зависимости от их результата.
x86 имеет немного задокументированную инструкцию salc, которая делает примерно это.
Конечно, вы можете добавить в язык новый оператор и определить его семантику, но это независимо от какой-либо реализации. Определение языка указывает только то, каким должен быть результат, а не способ его вычисления. Реализация компилятора должна сопоставить поведение с конкретными машинными инструкциями. И, благодаря правилу «как если бы», если компилятор может сгенерировать результат, используя не те инструкции, которые вы ожидаете, он может сделать это бесплатно.
Я знаю, и я согласен, Джон. Но в своей идее создания языка я бы никогда не стал добавлять функции, которые не поддерживаются по крайней мере в некоторых архитектурах. Это только мое личное мнение. Спектр языков высокого уровня уже достаточно хорошо охвачен, а для низкоуровневого программирования есть Си (если не ассемблер). Но я думаю, что C нужно переписать (особенно его плохую способность вычислять константные выражения во время компиляции). Я, вероятно, не буду отвечать за такую задачу, но мне все еще любопытно, как это можно сделать!
Ответы 4
Обновлено: как указывают другие люди, есть являются некоторые варианты «условно назначить 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 в качестве значения TRUE потребует тех же команд, только с другим операндом.
Ни одна из архитектур, с которыми я знаком, не реализует сравнение на равенство как «назначение 1 или 0 регистру общего назначения».
Спасибо, Сева. Это ответ на мой вопрос, я думаю!
Я считаю, что MIPS slt (установлено меньше чем) присваивает 1 или 0 регистру общего назначения.
x86 cmov работает только с операндами регистра или памяти, а не непосредственно. Но ваш код работает как псевдокод, если у вас есть значения в регистрах. За исключением того, что вы на самом деле xor ecx, ecx обнулите его, а затем cmp eax,ebx / cmove ecx, edi (где EDI содержит -1). Вы не стали бы использовать цепочку из 2 cmov инструкций, зависящих друг от друга, это излишне создавало бы дополнительную задержку.
Всего за 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 при применении этих трюков, и везде, где это возможно, он фактически вообще не сохраняет значение, а просто реорганизует ваш код, чтобы избежать его.
@rcgldr Но это не генерирует -1 для истинного, оно генерирует истинное для ложного.
@rcgldr, но инструкция ассемблера SETcc не имеет возможности установить значение - она может установить только 1 как истину, а не -1.
Я удалил свои предыдущие комментарии. Я удалю это позже.
Не существует реализации оператора 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 в одну микрооперацию; Я знаю, что это делается с другими распространенными парами команд. Не существует простой зависимости между потоком инструкций и количеством циклов.
Да, ты действительно понял, Снефтель! Это предложение полностью отвечает на мой вопрос: «Я подозреваю, что существование инструкций SETcc вызвало ваш вопрос, поскольку они преобразуют биты флагового регистра в значения 0/1. Нет соответствующей инструкции, которая переводит их в 0/~0”. Я знаю, что результат сравнения в большинстве случаев исчезает, но в контексте, где вы сохраняете результаты сравнения в битовых масках, это точно не так!
@madmurphy Осторожнее. Хотя нет эквивалента SETcc, который устанавливает все биты, в SSE-стране (где вы будете проводить большую часть своего времени, если вы действительно заботитесь об оптимизации) используются разные методы, и 0/~0, вероятно, будет быстрее, чем 0/1. Вот что я имею в виду под «различием в состоянии машины». См. godbolt.org/z/9xC-sF . Обратите внимание на инструкции vpsrld в случае 0/1, которые сдвигают вправо ~ 0, превращая его в 1.
Еще раз спасибо, Снефтель. Несмотря на то, что я неплохо разбираюсь в C, я действительно полный иностранец в мире ассемблера. Я бы задал вам такой вопрос: если бы вам пришлось разрабатывать свой собственный язык с нуля, включили бы вы такой оператор — назовем его «Равенство Чарли» (и, конечно, вам придется включить все остальные «Логические И Чарли», «Логическое ИЛИ Чарли» и так далее…)? В тех случаях, когда 0/~0 — это то, что действительно необходимо, думаете ли вы, что реализация таких операторов принесет пользу языку и его оптимизации?
Если бы я реализовывал язык, == выдавал бы логический результат, который не имел бы канонического целочисленного значения. (Другими словами, я бы сделал то же самое, что и практически любой язык, созданный за последние 20 лет.) не придавай большого значения ее низкоуровневым последствиям.
Мой вопрос был не о замене оператора == (в чем я с вами согласен, а о добавлении нового (набора) оператора(ов). Оператор == будет продолжать существовать в этом гипотетическом новом языке. Это теоретическая вопрос, поэтому вы не должны использовать «практичность» в качестве параметра для рассмотрения.Также этот оператор не «возвращает» логические значения, он «возвращает» числа (представьте, что он наполовину принадлежит к семейству побитовых операторов — хотя это логичный).
Нет, у меня не было бы такого оператора. Это будет просто синтаксический сахар для a == b ? X : Y для соответствующих X и Y, и он не будет использоваться достаточно часто, чтобы сделать его стоящим. И опять же, соображения оптимизации здесь не играют роли.
Забавный факт @Sneftel: в Ruby есть нечто, называемое object_id. Для обычных объектов это указатель, для небольших целых чисел это 2x+1. false имеет идентификатор объекта 0, а true имеет идентификатор объекта 20. Для nil это 8. Все зависит от реализации.
@Sneftel Я бы не стал недооценивать сахар!
Никакие x86 ISA не объединяют setcc. Согласно некоторым источникам, функция сравнения и ветвления составляет от 10 до 20% от общего количества инструкций для многих программ. Это единственный случай макрослияния, который реализуется любым процессором. (На самом деле SnB-семейство объединит add/sub, inc/dec или AND с JCC, но другие ограничены TEST и CMP). setcc/dec встречается гораздо реже, и его определенно не стоит объединять; реальный код почти всегда использует CMOV вместо создания маски 0/-1 и ее использования.
@madmurphy: Забавный факт, существует недокументированная инструкция 8086 SALC (установить AL из переноса), которая до сих пор поддерживается в 16/32-битном режиме современными процессорами Intel (и AMD?). Это в основном как sbb al,al без установки флажков: AL = CF ? -1 : 0. os2museum.com/wp/undocumented-8086-opcodes. Процессоры AMD даже распознают sbb same,same как независимую от старого значения регистра, зависящую только от CF, как xor-zero. На других процессорах sbb edx,edx действительно дает вам 0 / -1, но с ложной зависимостью от старого значения EDX.
@PeterCordes Это действительно интересно. На самом деле я думает о том, как спроектировать новый язык, который учится на C, но добавляет к этому мощную возможность постоянной оценки во время компиляции (самая мощная из когда-либо созданных), средства развертывания циклов, много низкоуровневого сахара. операторы, а также некоторые другие хорошие идеи. По сути, цель состоит в том, чтобы оставаться как можно более низкоуровневым, предоставляя разработчику даже больше контроля, чем C. Единственная абстракция более высокого уровня, чем CI может придумать в этом новом языке, — это некоторая поддержка методов объектов (хотя и реализованная немного иначе, чем C). на С++).
Сравнение векторов SIMD делать дает векторы результатов 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-код не может отдельно разветвляться на каждый элемент вектора без распаковки в скаляр и обратно. Он должен быть без ветвей. Как использовать условие if во встроенных функциях
например чтобы смешать 2 вектора на основе условия, без SSE4.1 pblendvb / blendvps, вы бы сравнили, а затем И / И НЕ / ИЛИ. например от Заменить байт другим
__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 asm.
Все это имеет отношение ничего к операторам C и неявному преобразованию логического значения в целочисленное.
В C и C++ операторы возвращают логическое значение true/false, которое в ассемблере для большинства машин для скалярного кода (не автоматически векторизованного) отображается в бит в регистре флагов.
Преобразование этого в целое число в регистре — совершенно отдельная вещь.
Но забавный факт: 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! Но это определенно изменения к лучшему.
Забавный факт, есть недокументированная инструкция 8086 SALC (установить AL из переноса) все еще поддерживается в 16/32-битном режиме современными процессорами Intel (и AMD?).
Это в основном похоже на sbb al,al без установки флагов: AL = CF ? -1 : 0. http://os2museum.com/wp/undocumented-8086-opcodes.
Вычитание с заимствованием с одним и тем же вводом дважды выполняет x-x - CF на x86, где CF — это заимствование для вычитания. И x-x, конечно же, всегда равен нулю. (На некоторых других ISA, таких как ARM, значение флага переноса противоположно вычитанию, C set означает «без заимствования».)
В общем, вы можете использовать sbb edx,edx (или любой другой регистр), чтобы преобразовать CF в целое число 0/-1. Но это работает только для CF; флаг переноса является особенным, и для других флагов нет ничего эквивалентного.
Некоторые процессоры AMD даже распознают sbb same,same как независимую от старого значения регистра, зависящую только от CF, например xor-zero. На других процессорах он по-прежнему имеет тот же архитектурный эффект, но с микроархитектурной ложной зависимостью от старого значения EDX.
Если вы разрабатываете ISA, который поддерживает такую операцию, и компилятор, который использует эту операцию, тогда конечно.