Когда/почему (a <0) потенциально веткится в выражении?

После прочтения многих комментариев по этому вопросу, есть пара людей (here и here), которые предполагают, что этот код:

int val = 5;
int r = (0 < val) - (val < 0); // this line here

приведет к ветвлению. К сожалению, ни один из них не дает никаких оправданий или не говорит, почему это вызвало бы ветвление (тристопия предполагает, что для этого требуется cmove -подобная инструкция или предикация, но на самом деле не говорит почему).

Являются ли эти люди правы в том, что "сравнение, используемое в выражении, не генерирует ветвь", на самом деле является мифом, а не фактом? (предполагая, что вы не используете какой-то эзотерический процессор). Если да, можете ли вы привести пример?

Я бы подумал, что не будет никакого ветвления (учитывая, что нет логического "короткого замыкания" ), и теперь мне любопытно.

+9
источник поделиться
3 ответа

Чтобы упростить дело, рассмотрим только одну часть выражения: val < 0. По сути, это означает, что если val отрицательно, верните 1, иначе 0 "; вы также можете написать его следующим образом:

val < 0 ? 1 : 0

Как это переводится в процессорные команды, в значительной степени зависит от компилятора и целевого процессора. Самый простой способ выяснить - написать простую тестовую функцию, например:

int compute(int val) {
    return val < 0 ? 1 : 0;
}

и просмотрите код ассемблера, который генерируется компилятором (например, с gcc -S -o - example.c). Для моей машины это происходит без ветвления. Однако, если я изменю его, чтобы вернуть 5 вместо 1, есть инструкции ветвления:

...
    cmpl    $0, -4(%rbp)
    jns     .L2
    movl    $5, %eax
    jmp     .L3
.L2:
    movl    $0, %eax
.L3:
...

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


Дополнение в ответ на это расширение/разъяснение:

Я спрашиваю, есть ли какая-либо (нормальная) платформа/компилятор, для которой ветка вероятна. MIPS/ARM/x86 (_64)/и т.д.. Все, что я ищу - это один случай, который демонстрирует, что это реальная возможность.

Это зависит от того, что вы считаете "разумной" платформой. Если почтенный семейство процессоров 6502 является нормальным, я думаю, что нет возможности рассчитать val > 0 на нем без ветвления. С другой стороны, большинство современных наборов инструкций предоставляют некоторый тип инструкции set-on-X.

(val < 0 может быть фактически вычислен без ветвления даже на 6502, поскольку он может быть реализован как сдвиг бит.)

+5
источник

Эмпиризм для победы:

int sign(int val) {
    return (0 < val) - (val < 0);
}

скомпилирован с оптимизацией. gcc (4.7.2) производит

sign:
.LFB0:
    .cfi_startproc
    xorl    %eax, %eax
    testl   %edi, %edi
    setg    %al
    shrl    $31, %edi
    subl    %edi, %eax
    ret
    .cfi_endproc

нет ветки. clang (3.2):

sign:                                   # @sign
    .cfi_startproc
# BB#0:
    movl    %edi, %ecx
    shrl    $31, %ecx
    testl   %edi, %edi
    setg    %al
    movzbl  %al, %eax
    subl    %ecx, %eax
    ret

ни. (на x86_64, Core i5)

+4
источник

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

+1
источник

Посмотрите другие вопросы по метке или Задайте вопрос