Suboptimal code generation for unsigned non-overflowing average

[uncleasm]

Discussed in depth in https://stackoverflow.com/questions/71019078/efficient-overflow-immune-arithmetic-mean-in-c-c

The optimal code for either

uint32_t avg(uint32_t a, uint32_t b) {
   return (a & b) + ((a ^ b) >> 1);
}
        mov     eax, esi
        and     eax, edi
        xor     esi, edi
        shr     esi
        add     eax, esi
        ret

uint32_t avg2(uint32_t a, uint32_t b) {
  return a/2 + b/2 + (a%2 + b%2)/2;
}
        mov     eax, edi
        shr     eax
        mov     ecx, esi
        shr     ecx
        add     eax, ecx
        and     edi, 1
        and     esi, 1
        add     esi, edi
        shr     esi
        add     eax, esi
        ret

uint32_t avg_by_widening(uint32_t a, uint32_t b) {
      return ((uint64_t)a + b) >> 1;
}

could use rotate through carry instruction on x64 backend, especially suitable as the replacement of avg_by_widening(uint64_t, uint64_t), which would need uint128_t as the intermediate variable type.

    add rax, rbx
    rcr rax, 1

[llvmbot]

@llvm/issue-subscribers-backend-x86

[uncleasm]

One possible workaround or added feature would be an new intrinsic __builtin_rotate_through_carry_right_u32:

uint32_t avg2(uint32_t a, uint32_t b) {
    uint32_t sum, carry_out;
    uint32_t carry_in = __builtin_add_overflow(a, b, &sum);
    return __builtin_rotate_through_carry_right_u32(sum, carry_in, &carry_out);
}

[topperc]

Does rcr gain much on recent Intel CPUs? Isn't it 3 uops with 2 cycles of latency?

[RKSimon]

CC @davemgreen who is current adding generic AVG dag node support

[uncleasm]

The code generated for the widening

    uint64_t widening_avg(uint64_t a, uint64_t b) { return ((unsigned __int128)a+b)/2; }
        xor     eax, eax
        add     rdi, rsi
        setb    al
        shld    rax, rdi, 63

In case of rcr being too slow, this code could be still improved to

     add     rdi, rsi
     adc     eax, eax;  or possibly   sbb eax, eax
     shld    rax, rdi, 63

[topperc]

The code generated for the widening

    uint64_t widening_avg(uint64_t a, uint64_t b) { return ((unsigned __int128)a+b)/2; }
        xor     eax, eax
        add     rdi, rsi
        setb    al
        shld    rax, rdi, 63

In case of rcr being too slow, this code could be still improved to

     add     rdi, rsi
     adc     eax, eax;  or possibly   sbb eax, eax
     shld    rax, rdi, 63

adc would require eax to be zeroed first wouldn’t it? At least bit 0. sbb doesn’t require zeroing for correctness, but it would wait for the last writer of eax unless a dependency breaking xor is done first.

[uncleasm]

adc eax,eax would shift what ever previous value there is in eax inserting the carry to bit position 0.
There indeed is the issue of eax having unwanted dependency, which could theoretically mitigated by selecting a least recently used register, if that makes any sense. sbb eax,eax should of course be detected as dependency breaking operation, but I guess it's not.

Another option is to recycle one of the source operands, which unfortunately does not help in returning the value in rax.

      add rdi, rsi
      adc rsi, rsi      ;    / adc rdi, rdi
      shld rsi, rdi, 63 ;    / shld rdi, rdi, 63

[s13n]

@topperc: I think the potential speed disadvantage of rcr could very easily be offset by lower register pressure and lower instruction bytecount. But it would come down to measuring it.

The solutions presented here round down in the case of an odd difference between a and b. Incidentally, the very similar std::midpoint from the C++20 library rounds towards a, which means that its result is one higher when a>b. The standard library seems to generate rather inefficient code, which contains branching and a multiplication (!). Better code on the x86 would be the following (64-bit version), but unfortunately most of it is for handling the peculiar rounding of std::midpoint:

xor	eax,eax
cmp	rdi,rsi
setnb	al
add	rdi,rsi
rcr	rdi,1
setc	dl
and	al,dl
add	rax,rdi

The result is left in register rax. The 32-bit version is the same except for register lengths.

As @uncleasm suggested, this could be implemented in C if the rcr instruction was available as an intrinsic. I haven't managed to find a way to make the compiler emit it as an optimization - it probably never emits the rcr or rcl instructions.

[RKSimon]

We now have ISD::AVG opcodes for this: https://reviews.llvm.org/D106237

So its just a question of ensuring SelectionDAG can recognise the code pattern and deciding on preferred x86 codegen output, there shouldn't be a need for "__builtin_rotate_through_carry_right_u32" etc.

[topperc]

I think having target independent builtins and IR intrinsics for avg and avgceil might make sense. Halide might be able to use them. As I understand it they currently use target specific vector intrinsics because having LLVM pattern match it was too fragile.

libc++ uses different code for integer std::midpoint that libstdc++. See https://reviews.llvm.org/D69459

LLVM will never generate rcr or rcl today.

[topperc]

@RKSimon the codegen for ushort for libc++ changed between LLVM 10 and LLVM 11. https://godbolt.org/z/Gnx5KnPcK see non_constexpr_short_newmp and non_constexpr_ushort_newmp

The code changed again in LLVM 12 and that broke the shld for int and uint. That seems to have been an IR change https://godbolt.org/z/GWTsWj5qG