[AVR] Fix miscompilation of zext + add

[aykevl]

Summary

Code like the following:

define i32 @foo(i32 %a, i1 zeroext %b) addrspace(1) {
entry:
  %conv = zext i1 %b to i32
  %add = add nsw i32 %conv, %a
  ret i32 %add
}

Would compile to the following (incorrect) code:

foo:
    mov     r18, r20
    clr     r19
    add     r22, r18
    adc     r23, r19
    sbci    r24, 0
    sbci    r25, 0
    ret

Those sbci instructions are clearly wrong, they should have been adc instructions.

This commit improves codegen to use adc instead:

foo:
    mov     r18, r20
    clr     r19
    ldi     r20, 0
    ldi     r21, 0
    add     r22, r18
    adc     r23, r19
    adc     r24, r20
    adc     r25, r21
    ret

This code is not optimal (it could be just 5 instructions instead of the current 9) but at least it doesn't miscompile.

---

WARNING: I don't know what I'm doing here. While removing that pattern works, I don't know why it's there or whether I just introduced a different bug.

[dylanmckay]

I'm not sure that this is a miscompile. Note that AVR has no "add with immediate" instruction, instead subsumed by the "subtract with immediate" instruction, which of course with immediate values being immediately known to the compiler, can be negated directly at the callsite to effectively form a "add with immediate" instruction.

In this case, with the two snippets

(trunk)

foo:
    mov     r18, r20
    clr     r19
    add     r22, r18
    adc     r23, r19
    sbci    r24, 0
    sbci    r25, 0
    ret

(with patch)

foo:
    mov     r18, r20
    clr     r19
    ldi     r20, 0
    ldi     r21, 0
    add     r22, r18
    adc     r23, r19
    adc     r24, r20
    adc     r25, r21
    ret

The first two instructions and the final ret are identical in both, let's remove.

(trunk)

add     r22, r18
adc     r23, r19
sbci    r24, 0
sbci    r25, 0

(with patch)

ldi     r20, 0
ldi     r21, 0
add     r22, r18
adc     r23, r19
adc     r24, r20
adc     r25, r21

With the patch, the LDIs and r20 and r21 aren't used until the last two ADCs, let's reorder

(with patch)

add     r22, r18
adc     r23, r19
ldi     r20, 0
ldi     r21, 0
adc     r24, r20
adc     r25, r21

This is equivalent assembly as before, and now the two snippets both have the exact same initial two add+adc instructions. Let's remove from both snippets, leaving

(trunk)

sbci    r24, 0
sbci    r25, 0

(with patch)

ldi     r20, 0
ldi     r21, 0
adc     r24, r20
adc     r25, r21

So the only possible difference between the two variants, is in the addition of last two bytes from the 32-bit zero extended i1 value.

The remaining (trunk) asm just subtracts zero from the upper half of the non-extended 32-bit integer %a in registers r24:r25. This is the compiler inserting an addition of the immediate 0 (as -0 = 0). This makes sense because the corresponding bits from the i1 value have to be zero because it was zero-extended to 32-bits. A subtraction of zero is always redundant, therefore the two SBCIs from the first patch are completely redundant, and could be removed by the compiler in a future optimization.

The remaining (with patch) asm just adds zero to the upper half of the non-zero extended 32-bit integer %a in registers r24:25 but with extra steps to load the zero value into a register.

The only two remaining patches are completely identical in terms of execution as far as I can tell.

In summary: I think this is not a miscompile, let me know if you still think otherwise.

[aykevl]

It took me much longer than it should to find a solid reproducer, but here is one:

// in one file
uint32_t add(uint32_t a, uint16_t b) {
    return a + b;
}

// in another file
uint32_t add(uint32_t a, uint16_t b);


// somewhere in the code of that file
uart_printint("add", add(0x7ffff, 1));

Adding 0x7ffff and 1 should result in 0x80000. However, without this patch it results in 0x60000.

Assembly without this patch:

d20:       64 0f           add     r22, r20
d22:       75 1f           adc     r23, r21
d24:       80 40           sbci    r24, 0x00       ; 0
d26:       90 40           sbci    r25, 0x00       ; 0
d28:       08 95           ret

With this patch:

d1c:       20 e0           ldi     r18, 0x00       ; 0
d1e:       30 e0           ldi     r19, 0x00       ; 0
d20:       64 0f           add     r22, r20
d22:       75 1f           adc     r23, r21
d24:       82 1f           adc     r24, r18
d26:       93 1f           adc     r25, r19
d28:       08 95           ret

A subtraction of zero is always redundant, therefore the two SBCIs from the first patch are completely redundant, and could be removed by the compiler in a future optimization.

The sbci not only subtracts an immediate (in this case zero), but it also subtracts the carry bit. Therefore it definitely does have an effect. This also is true for the last two adc instructions: they are needed to add the carry bit in case the previous add instruction caused a wraparound. However sbci and adc use the carry in the opposite direction (subtracting or adding it to their result).

Looking at AVRInstrInfo.td, I suspect there are a few more bugs around sbci.

I found this bug while trying to add AVR support to compiler-rt. One instance of the bug is here (the +=). I originally found it somewhere else, but had trouble finding the exact location again.

[dylanmckay]

Good reproduction, works exactly as expected and indeed this value is being miscalculated.

https://github.com/dylanmckay/avr-compiler-integration-tests/commit/481d69f92b25d267cdc9b74e61e37a31bb78f8c9

Thanks for the patch Ayke.

[aykevl]

Patch committed!

I looked for other instances of this bug, see below.

def : Pat<(add i16:$src1, imm0_63_neg:$src2),
          (SBIWRdK i16:$src1, (imm0_63_neg:$src2))>;
def : Pat<(add i16:$src1, imm:$src2),
          (SUBIWRdK i16:$src1, (imm16_neg_XFORM imm:$src2))>;

Both don't involve a carry bit, so should be fine.

def : Pat<(addc i16:$src1, imm:$src2),
          (SUBIWRdK i16:$src1, (imm16_neg_XFORM imm:$src2))>;

addc means "add with carry" while subiw is expanded to subi/sbci which discards the incoming carry bit. This may be a bug.

def : Pat<(add i8:$src1, imm:$src2),
          (SUBIRdK i8:$src1, (imm8_neg_XFORM imm:$src2))>;

No carry bits, so should be fine.

def : Pat<(addc i8:$src1, imm:$src2),
          (SUBIRdK i8:$src1, (imm8_neg_XFORM imm:$src2))>;

Like addc i16, this discards the carry bit so may be a bug.

def : Pat<(adde i8:$src1, imm:$src2),
          (SBCIRdK i8:$src1, (imm8_neg_XFORM imm:$src2))>;

adde means an add with a carry input and carry output. The sbci instruction does the same thing, except that it uses the carry in the wrong direction (subtracting instead of adding). Basically the 8-bit version of the bug this patch is about.

I don't have any reproducers/proofs, but will leave this here for future reference.

[aykevl]

I suspect the patterns are technically a bug, but may not show up in practice if they're all buggy in the exact same way. If all additions in a chain are replaced with subtractions, then it should work.

llvm/lib/Target/AVR/AVRInstrInfo.td

 // These patterns convert add (x, -imm) to sub (x, imm) since we dont have
 // any add with imm instructions. Also take care of the adiw/sbiw instructions.
 def : Pat<(add i16:$src1, imm0_63_neg:$src2),
           (SBIWRdK i16:$src1, (imm0_63_neg:$src2))>;
 def : Pat<(add i16:$src1, imm:$src2),
           (SUBIWRdK i16:$src1, (imm16_neg_XFORM imm:$src2))>;
 def : Pat<(addc i16:$src1, imm:$src2),
           (SUBIWRdK i16:$src1, (imm16_neg_XFORM imm:$src2))>;
-def : Pat<(adde i16:$src1, imm:$src2),
-          (SBCIWRdK i16:$src1, (imm16_neg_XFORM imm:$src2))>;
 
 def : Pat<(add i8:$src1, imm:$src2),
           (SUBIRdK i8:$src1, (imm8_neg_XFORM imm:$src2))>;
 def : Pat<(addc i8:$src1, imm:$src2),
           (SUBIRdK i8:$src1, (imm8_neg_XFORM imm:$src2))>;
 def : Pat<(adde i8:$src1, imm:$src2),
           (SBCIRdK i8:$src1, (imm8_neg_XFORM imm:$src2))>;
 

llvm/test/CodeGen/AVR/add.ll

 define i16 @add16_reg_imm_subi(i16 %a) {
 ; CHECK-LABEL: add16_reg_imm_subi:
 ; CHECK: subi r24, 133
 ; CHECK: sbci r25, 255
     %result = add i16 %a, 123
     ret i16 %result
 }
 
+define i16 @add16_reg_reg_zext(i16 %a, i1 zeroext %b) {
+; CHECK-LABEL: add16_reg_reg_zext:
+; CHECK: mov r18, r22
+; CHECK: clr r19
+; CHECK: add r24, r18
+; CHECK: adc r25, r19
+    %zext = zext i1 %b to i16
+    %result = add i16 %a, %zext
+    ret i16 %result
+}
+
 define i32 @add32_reg_reg(i32 %a, i32 %b) {
 ; CHECK-LABEL: add32_reg_reg:
 ; CHECK: add r22, r18
 ; CHECK: adc r23, r19
 ; CHECK: adc r24, r20
 ; CHECK: adc r25, r21
     %result = add i32 %a, %b
     ret i32 %result
 }
 
 define i32 @add32_reg_imm(i32 %a) {
 ; CHECK-LABEL: add32_reg_imm:
 ; CHECK: subi r22, 251
 ; CHECK: sbci r23, 255
 ; CHECK: sbci r24, 255
 ; CHECK: sbci r25, 255
     %result = add i32 %a, 5
     ret i32 %result
 }
 
+define i32 @add32_reg_reg_zext(i32 %a, i1 zeroext %b) {
+; CHECK-LABEL: add32_reg_reg_zext:
+; CHECK: mov r18, r20
+; CHECK: clr r19
+; CHECK: ldi r20, 0
+; CHECK: ldi r21, 0
+; CHECK: add r22, r18
+; CHECK: adc r23, r19
+; CHECK: adc r24, r20
+; CHECK: adc r25, r21
+    %zext = zext i1 %b to i32
+    %result = add i32 %a, %zext
+    ret i32 %result
+}
+
 define i64 @add64_reg_reg(i64 %a, i64 %b) {
 ; CHECK-LABEL: add64_reg_reg:
 ; CHECK: add r18, r10
 ; CHECK: adc r20, r12
 ; CHECK: adc r21, r13
 ; CHECK: adc r22, r14
 ; CHECK: adc r23, r15
 ; CHECK: adc r24, r16

 ; CHECK: sbci r21, 255
 ; CHECK: sbci r22, 255
 ; CHECK: sbci r23, 255
 ; CHECK: sbci r24, 255
 ; CHECK: sbci r25, 255
     %result = add i64 %a, 5
     ret i64 %result
 }
+
+define i64 @add64_reg_reg_zext(i64 %a, i1 zeroext %b) {
+; CHECK-LABEL: add64_reg_reg_zext:
+; CHECK: mov r30, r16
+; CHECK: clr r31
+; CHECK: ldi r26, 0
+; CHECK: ldi r27, 0
+; CHECK: add r18, r30
+; CHECK: adc r19, r31
+; CHECK: adc r20, r26
+; CHECK: adc r21, r27
+; CHECK: adc r22, r26
+; CHECK: adc r23, r27
+; CHECK: adc r24, r26
+; CHECK: adc r25, r27
+    %zext = zext i1 %b to i64
+    %result = add i64 %a, %zext
+    ret i64 %result
+}