Out-of-order execution in C#

Admin 1
Viewed 188

I have the following snippet:

static long F(long a, long b, long c, long d) 
{
    return a + b + c + d;
}

which generates:

<Program>$.<<Main>$>g__F|0_0(Int64, Int64, Int64, Int64)
    L0000: add rdx, rcx
    L0003: lea rax, [rdx+r8]
    L0007: add rax, r9
    L000a: ret

If I understand correctly from this (§ Out of order execution) manual: The code above translates to ((a + b) + c) + d. And to compute this the CPU has to wait for the 1st parenthesis and for the 2nd and so on. In here we see that LEA is in the middle which means that they can't be executed in parallel (if I understood that correctly). So what the writer suggests is:

writing parenthesis on "independent" pairs:

static long G(long a, long b, long c, long d) 
{
    return (a + b) + (c + d);
}

but this generates the same assembly:

<Program>$.<<Main>$>g__G|0_1(Int64, Int64, Int64, Int64)
    L0000: add rdx, rcx
    L0003: lea rax, [rdx+r8]
    L0007: add rax, r9
    L000a: ret

In contrast this is what GCC (O2) generates for C code:

int64_t
f(int64_t a, int64_t b, int64_t c, int64_t d) {
        return a + b + c + d;
}

int64_t
g(int64_t a, int64_t b, int64_t c, int64_t d) {
        return (a + b) + (c + d);
}

here is the output:

f: 
        add     rcx, rdx        ; I guess -O2 did the job for me.
        add     rcx, r8         ; I guess -O2 did the job for me.
        lea     rax, [rcx+r9]
        ret
g:
        add     rcx, rdx
        add     r8, r9
        lea     rax, [rcx+r8]
        ret

Question

  • Did I understand the manual correctly? Should the 2 ADDs come with each other (no LEA in the middle)? If yes how can I hint the C# compiler to not ignore my parenthesis?

Notes

compiler-optimization x86-64 assembly cpu-architecture c#
1 Answers

Integer addition is associative. Compilers can take advantage of this (the "as-if rule"), regardless of the source-level order of operations.

(Unfortunately it seems most compilers are doing a bad job at this and making it worse even if you write your source cleverly.)

There's no side-effect for integer overflow in asm; even on targets like MIPS where add traps on signed-overflow, compilers use addu which doesn't, so they can optimize. (In C, compilers can assume the source-level order of operations never overflows, because that would be Undefined Behaviour. So they could use trapping add on ISAs that have it, for calculations that happen with the same inputs in the C abstract machine. But even though gcc -fwrapv to give signed-integer overflow well-defined 2's complement wraparound behaviour is not the default, compilers do use instructions that may allow silent wrapping, not trapping. Mostly so they don't have to care about whether any given operation is on values that appear in the C abstract machine or not. UB doesn't mean required-to-fault; -fsanitize=undefined takes extra code to make that happen.)

e.g. INT_MAX + INT_MIN + 1 could be evaluated as INT_MAX + 1 (overflowing to INT_MIN), then . + INT_MIN overflowing back to 0 on a 2's complement machine, or in source order with no overflows. Same final result, and that's all that's logically visible from the operation.

CPUs with out-of-order exec don't try to re-associate instructions, though, they follow the dependency graph from the asm / machine code.

(For one thing, that's too much for hardware to consider on the fly, and for another, the FLAGS output of each operation does depend on which temporaries you create, and an interrupt could arrive at any point. So the proper architectural state needs to be recoverable at instruction boundaries when all older instructions have finished. That means it's the compiler's job to expose instruction-level parallelism in the asm, not for the hardware to use math to create it. See also Modern Microprocessors A 90-Minute Guide! and this answer)

So how did compilers do?

Mostly badly, shooting themselves in the foot / pessimizing your attempt at doing this source-level optimization, at least in this case.

  • C#: removes ILP even if it exists in the source; serializes (a+b) + (c+d) into one linear chain of operations; 3 cycle latency.

  • clang12.0: same, serializes both versions.

  • MSVC: same, serializes both versions.

  • GCC11.1 for signed int64_t: preserves source order of operations. It's a longstanding GCC missed-optimization bug that its optimizer avoids introducing signed-overflow even in temporaries for some reason, like it backwards as far as the promises / guarantees / optimization opportunities that something being UB in the abstract machine creates when making a concrete implementation that runs as if on the abstract machine. Although GCC does know it can auto-vectorize int addition; it's only reordering within a scalar expression where some overly-conservative check lumps signed integer in with floating-point as non-associative.

  • GCC11.1 for uint64_t or with -fwrapv: treats as associative and compiles f and g the same way. Serializes with most tuning options (including for other ISAs like MIPS or PowerPC), but -march=znver1 happens to create ILP. (This does not mean that only AMD Zen is superscalar, it means GCC has missed-optimization bugs!)

  • ICC 2021.1.2: creates ILP even in the linear source version (f), but uses add/mov instead of LEA as the final step. :/

Godbolt for clang/MSVC/ICC.

Godbolt for GCC signed / unsigned or with -fwrapv.

Ideal is to start with two independent additions, then combine the pairs. One of those three additions should be done with an lea to get a result into RAX, but it can be any of the three. In a stand-alone function, you're allowed to destroy any of the incoming arg-passing registers and there's no real reason to avoid overwriting two of them instead of just one.

You do only want one LEA because a 2-register addressing mode makes it a longer instruction than an ADD.

user_2241320
Related