[DAG] Promote ADDCARRY / SUBCARRY

Add missing case that was not implemented yet.

Differential Revision: https://reviews.llvm.org/D38942

llvm-svn: 320567

2 files changed, 84 insertions, 1 deletions

diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
index d232641303d..ec8d6db66f7 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
@@ -772,7 +772,30 @@ SDValue DAGTypeLegalizer::PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo) {
 SDValue DAGTypeLegalizer::PromoteIntRes_ADDSUBCARRY(SDNode *N, unsigned ResNo) {
   if (ResNo == 1)
     return PromoteIntRes_Overflow(N);
-  llvm_unreachable("Not implemented");
+
+  // We need to sign-extend the operands so the carry value computed by the
+  // wide operation will be equivalent to the carry value computed by the
+  // narrow operation.
+  // An ADDCARRY can generate carry only if any of the operands has its
+  // most significant bit set. Sign extension propagates the most significant
+  // bit into the higher bits which means the extra bit that the narrow
+  // addition would need (i.e. the carry) will be propagated through the higher
+  // bits of the wide addition.
+  // A SUBCARRY can generate borrow only if LHS < RHS and this property will be
+  // preserved by sign extension.
+  SDValue LHS = SExtPromotedInteger(N->getOperand(0));
+  SDValue RHS = SExtPromotedInteger(N->getOperand(1));
+
+  EVT ValueVTs[] = {LHS.getValueType(), N->getValueType(1)};
+
+  // Do the arithmetic in the wide type.
+  SDValue Res = DAG.getNode(N->getOpcode(), SDLoc(N), DAG.getVTList(ValueVTs),
+                            LHS, RHS, N->getOperand(2));
+
+  // Update the users of the original carry/borrow value.
+  ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
+
+  return SDValue(Res.getNode(), 0);
 }
 
 SDValue DAGTypeLegalizer::PromoteIntRes_XMULO(SDNode *N, unsigned ResNo) {
diff --git a/llvm/test/CodeGen/ARM/addsubcarry-promotion.ll b/llvm/test/CodeGen/ARM/addsubcarry-promotion.ll
new file mode 100644
index 00000000000..8b99b2ada7c
--- /dev/null
+++ b/llvm/test/CodeGen/ARM/addsubcarry-promotion.ll
@@ -0,0 +1,60 @@
+; RUN: llc -O2 -mtriple armv7a < %s | FileCheck --check-prefix=ARM %s
+
+; RUN: llc -O2 -mtriple thumbv6m < %s | FileCheck --check-prefix=THUMB1 %s
+; RUN: llc -O2 -mtriple thumbv8m.base < %s | FileCheck --check-prefix=THUMB1 %s
+
+; RUN: llc -O2 -mtriple thumbv7a < %s | FileCheck --check-prefix=THUMB %s
+; RUN: llc -O2 -mtriple thumbv8m.main < %s | FileCheck --check-prefix=THUMB %s
+
+define void @fn1(i32 %a, i32 %b, i32 %c) local_unnamed_addr #0 {
+entry:
+
+; ARM: rsb	r2, r2, #1
+; ARM: adds	r0, r1, r0
+; ARM: movw	r1, #65535
+; ARM: sxth	r2, r2
+; ARM: adc	r0, r2, #0
+; ARM: tst	r0, r1
+; ARM: bxeq	lr
+; ARM: .LBB0_1:
+; ARM: b	.LBB0_1
+
+; THUMB1: movs	r3, #1
+; THUMB1: subs	r2, r3, r2
+; THUMB1: sxth	r2, r2
+; THUMB1: movs	r3, #0
+; THUMB1: adds	r0, r1, r0
+; THUMB1: adcs	r3, r2
+; THUMB1: lsls	r0, r3, #16
+; THUMB1: beq	.LBB0_2
+; THUMB1: .LBB0_1:
+; THUMB1: b	.LBB0_1
+
+; THUMB: rsb.w	r2, r2, #1
+; THUMB: adds	r0, r0, r1
+; THUMB: sxth	r2, r2
+; THUMB: adc	r0, r2, #0
+; THUMB: lsls	r0, r0, #16
+; THUMB: it	eq
+; THUMB: bxeq	lr
+; THUMB: .LBB0_1:
+; THUMB: b	.LBB0_1
+
+  %add = add i32 %b, %a
+  %cmp = icmp ult i32 %add, %b
+  %conv = zext i1 %cmp to i32
+  %sub = sub i32 1, %c
+  %add1 = add i32 %sub, %conv
+  %conv2 = trunc i32 %add1 to i16
+  %tobool = icmp eq i16 %conv2, 0
+  br i1 %tobool, label %if.end, label %for.cond.preheader
+
+for.cond.preheader:                               ; preds = %entry
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond.preheader, %for.cond
+  br label %for.cond
+
+if.end:                                           ; preds = %entry
+  ret void
+}