Is the conditional move optimization against the C standard?

Question

It is a common optimization to use conditional move (assembly cmov) to optimize the conditional expression ?: in C. However, the C standard says:

The first operand is evaluated; there is a sequence point between its evaluation and the evaluation of the second or third operand (whichever is evaluated). The second operand is evaluated only if the first compares unequal to 0; the third operand is evaluated only if the first compares equal to 0; the result is the value of the second or third operand (whichever is evaluated), converted to the type described below.110)

For example, the following C code

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int c= a > b ? a + 1 : 2 + b;
    printf("%d", c);
    return 0;
}

will generate optimized related asm code as follows:

call    __isoc99_scanf
movl    (%rsp), %esi
movl    4(%rsp), %ecx
movl    $1, %edi
leal    2(%rcx), %eax
leal    1(%rsi), %edx
cmpl    %ecx, %esi
movl    $.LC1, %esi
cmovle  %eax, %edx
xorl    %eax, %eax
call    __printf_chk

According to the standard, the conditional expression will only have one branch evaluated. But here both branches are evaluated, which is against the standard's semantics. Is this optimization against the C standard? Or do many compiler optimizations have something inconsistent with the language standard?

If the compiler can prove the behavior is the same then it can of course use `cmov`. Otherwise it's a bug. — Jester, May 21 '18 at 19:36
An optimisation technique by itself cannot be "against the standard". A compiler that applies an optimisation technique which produces invalid program behaviour simply has a bug. — n. m. could be an AI, May 21 '18 at 19:38
@immibis I've updated the asm code, which is inconsistent with the c code previously. Both are evaluated by the `lea` command, which effectively add two numbers (but does not set condition flags). — yeshengm, May 22 '18 at 05:43
@manifold: You're missing the point. How can *a conforming C program* tell the difference? Looking at / disassembling its own machine code isn't part of what the C standard guarantees you can do. This is just another way of pointing out that the as-if rule allows it. — Peter Cordes, May 22 '18 at 05:45

Antti Haapala -- Слава Україні · Accepted Answer · 2018-05-22T10:04:25.723

The optimization is legal, due to the "as-if rule", i.e. C11 5.1.2.3p6.

A conforming implementation is just required to produce a program that when run produces the same observable behaviour as the execution of the program using the abstract semantics would have produced. The rest of the standard just describes these abstract semantics.

What the compiled program does internally does not matter at all, the only thing that matters is that when the program ends it does not have any other observable behaviour, except reading the a and b and printing the value of a + 1 or b + 2 depending on which one a or bis greater, unless something occurs that causes the behaviour be undefined. (Bad input causes a, b be uninitialized and therefore accesses undefined; range error and signed overflow can occur too.) If undefined behaviour occurs, then all bets are off.

Since accesses to volatile variables must be evaluated strictly according to the abstract semantics, you can get rid of the conditional move by using volatile here:

#include <stdio.h>

int main() {
    volatile int a, b;
    scanf("%d %d", &a, &b);
    int c = a > b ? a + 1 : 2 + b;
    printf("%d", c);
    return 0;
}

compiles to

        call    __isoc99_scanf@PLT
        movl    (%rsp), %edx
        movl    4(%rsp), %eax
        cmpl    %eax, %edx
        jg      .L7
        movl    4(%rsp), %edx
        addl    $2, %edx
.L3:
        leaq    .LC1(%rip), %rsi
        xorl    %eax, %eax
        movl    $1, %edi
        call    __printf_chk@PLT

        [...]

.L7:
        .cfi_restore_state
        movl    (%rsp), %edx
        addl    $1, %edx
        jmp     .L3

by my GCC Ubuntu 7.2.0-8ubuntu3.2

@ArturBiesiadowski: Good point: the definition of observable in the C standard doesn't include performance, and is strictly limited to what can be *portably* observed by a conforming C program (with no UB like `(char*)my_func`), so that rules out checking for branchy / branchless by profiling with predictable / unpredictable data ([Why is it faster to process a sorted array than an unsorted array?](https://stackoverflow.com/q/11227809)). This is why compiling with debug-mode de-optimization and full optimization (keeping things in registers, and even auto-vectorization) are both legal. — Peter Cordes, May 22 '18 at 10:12

score 26 · Answer 2 · answered May 21 '18 at 19:38

26

The C Standard describes an abstract machine executing C code. A compiler is free to perform any optimization as long as that abstraction is not violated, i.e. a conforming program cannot tell the difference.

answered May 21 '18 at 19:38

Jens

69,818
15
125
179

14

In particular, as long as the 2nd/3rd operands don't have any visibile side effect, the compiler can evaluate them both always without the standard being violated in any way. – Matteo Italia May 21 '18 at 19:41
According to the standard, "evaluation of an expression in general includes both value computations and initiation of side effects". But here the compiler generates code that does this computation whereas the standard requires only one operand to be evaluated. That's where I'm confused. – yeshengm May 21 '18 at 19:50
2

@manifold: Yes, but from the point of view of the abstract machine, only one was evaluated. – Acorn May 21 '18 at 20:02
1

@manifold The program can't tell whether it was evaluated, so does it matter? – user253751 May 22 '18 at 05:50
1

@manifold Yes, but in this case there are no side effects to initiate, so as far as the observable behaviour is concerned, only one was evaluated. In the generated assembly, actual computation of the non-evaluated operand also incidentally happens, but it's not observable. – Angew is no longer proud of SO May 22 '18 at 08:50
As per the standard, evaluation is computation *and* side effects in the abstract machine. I think the *and* makes sense. it's not "or"! i.e. an expression is considered evaluated iff it results in some side effects. – yeshengm May 22 '18 at 11:37
@manifold yes but there is no side effect here is it? Try it with side effects and if it executes then you have a bug. – Kami Kaze May 22 '18 at 14:44

Is the conditional move optimization against the C standard?

2 Answers2