Sub-optimal codegen when adding with carry

[andrepd]

Consider the following Rust code (no need to know Rust, it's very straightforward).

pub fn f1(q: &mut [u64; 8], implicit: u64) {
    let mut carry = false;
    for i in 0 .. q.len() {
        let (r, o) = u64::carrying_add(q[i], implicit, carry);  // Add q[i] + implicit + carry, return tuple with "result modulo 2^64" and "new carry"
        q[i] = r;
        carry = o;
    }
}

On x86, this gets compiled to what you would expect.

add     qword ptr [rdi], rsi
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi
ret

However, if you take the carry as a parameter, rather than initialising it to zero

pub fn f2(q: &mut [u64; 8], implicit: u64, mut carry: bool) {
    for i in 0 .. q.len() {
        let (r, o) = u64::carrying_add(q[i], implicit, carry);
        q[i] = r;
        carry = o;
    }
}

I would expect it to be compiled to

add     dl, -1  ; Set carry flag to 0/1 if dl is 0/1 resp
adc     qword ptr [rdi], rsi
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi
ret

However llvm (via rustc) writes it instead in a very roundabout way:

mov     rax, qword ptr [rdi]
add     rax, rsi
setb    cl
mov     edx, edx
add     rdx, rax
setb    al
or      al, cl
mov     qword ptr [rdi], rdx
add     al, -1
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi

This is a godbolt illustrating this. https://godbolt.org/z/9M1Tr4cGj

This is the equivalent godbolt, but in C++: https://godbolt.org/z/sKz5vrEjr . If you look at this one, you can switch to gcc to see how it gets it right.

All my attempts to nudge codegen into the optimsed form (e.g. by explicitly writing something like let (dummy, o) = u64::carrying_add(0, u64::MAX, carry); carry = 0) have failed. This interests me because the optimised codegen cuts an inner loop in a program of mine in half! :)

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: None (andrepd)

Consider the following Rust code (no need to know Rust, it's very straightforward).

pub fn f1(q: &mut [u64; 8], implicit: u64) {
    let mut carry = false;
    for i in 0 .. q.len() {
        let (r, o) = u64::carrying_add(q[i], implicit, carry);  // Add q[i] + implicit + carry, return tuple with "result modulo 2^64" and "new carry"
        q[i] = r;
        carry = o;
    }
}

On x86, this gets compiled to what you would expect.

add     qword ptr [rdi], rsi
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi
ret

However, if you take the carry as a parameter, rather than initialising it to zero

pub fn f2(q: &mut [u64; 8], implicit: u64, mut carry: bool) {
    for i in 0 .. q.len() {
        let (r, o) = u64::carrying_add(q[i], implicit, carry);
        q[i] = r;
        carry = o;
    }
}

I would expect it to be compiled to

add     dl, -1  ; Set carry flag to 0 if 
adc     qword ptr [rdi], rsi
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi
ret

However llvm (via rustc) writes it instead in a very roundabout way:

mov     rax, qword ptr [rdi]
add     rax, rsi
setb    cl
mov     edx, edx
add     rdx, rax
setb    al
or      al, cl
mov     qword ptr [rdi], rdx
add     al, -1
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi

This is a godbolt illustrating this. https://godbolt.org/z/9M1Tr4cGj

This is the equivalent godbolt, but in C++: https://godbolt.org/z/sKz5vrEjr . If you look at this one, you can switch to gcc to see how it gets it right.

All my attempts to nudge codegen into the optimsed form (e.g. by explicitly writing something like let (dummy, o) = u64::carrying_add(0, u64::MAX, carry); carry = 0) have failed. This interests me because the optimised codegen cuts an inner loop in a program of mine in half! :)

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: None (andrepd)

Consider the following Rust code (no need to know Rust, it's very straightforward).

pub fn f1(q: &mut [u64; 8], implicit: u64) {
    let mut carry = false;
    for i in 0 .. q.len() {
        let (r, o) = u64::carrying_add(q[i], implicit, carry);  // Add q[i] + implicit + carry, return tuple with "result modulo 2^64" and "new carry"
        q[i] = r;
        carry = o;
    }
}

On x86, this gets compiled to what you would expect.

add     qword ptr [rdi], rsi
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi
ret

However, if you take the carry as a parameter, rather than initialising it to zero

pub fn f2(q: &mut [u64; 8], implicit: u64, mut carry: bool) {
    for i in 0 .. q.len() {
        let (r, o) = u64::carrying_add(q[i], implicit, carry);
        q[i] = r;
        carry = o;
    }
}

I would expect it to be compiled to

add     dl, -1  ; Set carry flag to 0 if 
adc     qword ptr [rdi], rsi
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi
ret

However llvm (via rustc) writes it instead in a very roundabout way:

mov     rax, qword ptr [rdi]
add     rax, rsi
setb    cl
mov     edx, edx
add     rdx, rax
setb    al
or      al, cl
mov     qword ptr [rdi], rdx
add     al, -1
adc     qword ptr [rdi + 8], rsi
adc     qword ptr [rdi + 16], rsi
adc     qword ptr [rdi + 24], rsi
adc     qword ptr [rdi + 32], rsi
adc     qword ptr [rdi + 40], rsi
adc     qword ptr [rdi + 48], rsi
adc     qword ptr [rdi + 56], rsi

This is a godbolt illustrating this. https://godbolt.org/z/9M1Tr4cGj

This is the equivalent godbolt, but in C++: https://godbolt.org/z/sKz5vrEjr . If you look at this one, you can switch to gcc to see how it gets it right.

All my attempts to nudge codegen into the optimsed form (e.g. by explicitly writing something like let (dummy, o) = u64::carrying_add(0, u64::MAX, carry); carry = 0) have failed. This interests me because the optimised codegen cuts an inner loop in a program of mine in half! :)

[RKSimon]

This is what combineCarryDiamond should be handling

[RKSimon]

reduced f2:

define void @f2(ptr noundef captures(none) %q, i64 noundef %implicit, i1 noundef zeroext %carry) {
entry:
  %0 = load i64, ptr %q, align 8
  %1 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %0, i64 %implicit)
  %2 = extractvalue { i64, i1 } %1, 1
  %3 = extractvalue { i64, i1 } %1, 0
  %conv1.i = zext i1 %carry to i64
  %4 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %3, i64 %conv1.i)
  %5 = extractvalue { i64, i1 } %4, 1
  %6 = extractvalue { i64, i1 } %4, 0
  %or3.i = or i1 %2, %5
  store i64 %6, ptr %q, align 8
  %arrayidx.1 = getelementptr inbounds nuw i8, ptr %q, i64 8
  %7 = load i64, ptr %arrayidx.1, align 8
  %8 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %7, i64 %implicit)
  %9 = extractvalue { i64, i1 } %8, 0
  %conv1.i.1 = zext i1 %or3.i to i64
  %10 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %9, i64 %conv1.i.1)
  %11 = extractvalue { i64, i1 } %10, 0
  store i64 %11, ptr %arrayidx.1, align 8
  ret void
}

f2: # @f2
# %bb.0: # %entry
  movq (%rdi), %rax
  addq %rsi, %rax
  setb %cl
  movl %edx, %edx
  addq %rax, %rdx
  setb %al
  orb %cl, %al
  movq %rdx, (%rdi)
  addq 8(%rdi), %rsi
  movzbl %al, %eax
  addq %rsi, %rax
  movq %rax, 8(%rdi)
  retq
  # -- End function

but could be:

  addb $-1, %dl
  adcq %rsi, (%rdi)
  adcq %rsi, 8(%rdi)
  retq