[Thumb1] combine ADDC/SUBC with a negative immediate

[tyomitch]

Summary

This simple optimization has been split out of https://reviews.llvm.org/D30400

[rengolin]

Can you make sure this works with inline asm? We had a trick in the to make it work (Linux stuff), so I just want to make sure it follows the same path on both cases.

[tyomitch]

Can you make sure this works with inline asm? We had a trick in the to make it work (Linux stuff)

Can you suggest a test case? I'm not quite sure how ADDC/SUBC, inline asm, and Linux all relate to each other.

[rengolin]

Right, sorry, this has nothing to do with the assembler, and is only to perform better codegen. Ignore my comments. LGTM. Thanks!

[zzheng]

This patch needs to be reverted or appended. I'll try to send a test case.

llvm/trunk/lib/Target/ARM/ARMISelLowering.cpp

9671 ↗

(On Diff #91636)

There's a corner case when imm is -2147483648, that's -2^31 and 0x80000000 in two's compliment.

SignExt this value and flip its sign in int64_t, it's still 0x80000000 and interpreted as -2^31 by i32 type.

So we have infinite loop here where this function consume and produce the same node forever.

[zzheng]

This test case reproduce the problem (infinite compile time)

define i64 @f6(i64 %x, i64 %y) {
entry:

%tmp1 = add i64 %y, -2147483648           ; <i64> [#uses=1]
ret i64 %tmp1

}

lib/Target/ARM/ARMISelLowering.cpp

if ((AddcNode->getOpcode() == ARMISD::ADDC) &&
     return DAG.getNode(ARMISD::UMAAL, SDLoc(N),
                        DAG.getVTList(MVT::i32, MVT::i32),
                        {N->getOperand(0), N->getOperand(1),
                         AddcNode->getOperand(0), AddcNode->getOperand(1)});
   else
     return SDValue();
 }
 
+static SDValue PerformAddcSubcCombine(SDNode *N, SelectionDAG &DAG,
+                                      const ARMSubtarget *Subtarget) {
+  if (Subtarget->isThumb1Only()) {
+    SDValue RHS = N->getOperand(1);
+    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHS)) {
+      int64_t imm = C->getSExtValue();
+      if (imm < 0) {
+        SDLoc DL(N);
+        RHS = DAG.getConstant(-imm, DL, MVT::i32);
+        unsigned Opcode = (N->getOpcode() == ARMISD::ADDC) ? ARMISD::SUBC
+                                                           : ARMISD::ADDC;
+        return DAG.getNode(Opcode, DL, N->getVTList(), N->getOperand(0), RHS);
+      }
+    }
+  }
+  return SDValue();
+}
+
 static SDValue PerformAddeSubeCombine(SDNode *N, SelectionDAG &DAG,
                                       const ARMSubtarget *Subtarget) {
   if (Subtarget->isThumb1Only()) {
     SDValue RHS = N->getOperand(1);
     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHS)) {
       int64_t imm = C->getSExtValue();
       if (imm < 0) {
         SDLoc DL(N);
SDValue ARMTargetLowering::PerformDAGCombine(SDNode *N,
   case ARMISD::ADDE:    return PerformADDECombine(N, DCI, Subtarget);
   case ARMISD::UMLAL:   return PerformUMLALCombine(N, DCI.DAG, Subtarget);
   case ISD::ADD:        return PerformADDCombine(N, DCI, Subtarget);
   case ISD::SUB:        return PerformSUBCombine(N, DCI);
   case ISD::MUL:        return PerformMULCombine(N, DCI, Subtarget);
   case ISD::OR:         return PerformORCombine(N, DCI, Subtarget);
   case ISD::XOR:        return PerformXORCombine(N, DCI, Subtarget);
   case ISD::AND:        return PerformANDCombine(N, DCI, Subtarget);
+  case ARMISD::ADDC:
+  case ARMISD::SUBC:    return PerformAddcSubcCombine(N, DCI.DAG, Subtarget);
   case ARMISD::SUBE:    return PerformAddeSubeCombine(N, DCI.DAG, Subtarget);
   case ARMISD::BFI:     return PerformBFICombine(N, DCI);
   case ARMISD::VMOVRRD: return PerformVMOVRRDCombine(N, DCI, Subtarget);
   case ARMISD::VMOVDRR: return PerformVMOVDRRCombine(N, DCI.DAG);
   case ISD::STORE:      return PerformSTORECombine(N, DCI);
   case ISD::BUILD_VECTOR: return PerformBUILD_VECTORCombine(N, DCI, Subtarget);
   case ISD::INSERT_VECTOR_ELT: return PerformInsertEltCombine(N, DCI);
   case ISD::VECTOR_SHUFFLE: return PerformVECTOR_SHUFFLECombine(N, DCI.DAG);

lib/Target/ARM/ARMInstrThumb.td

 //
 
 // Comparisons
 def : T1Pat<(ARMcmpZ tGPR:$Rn, imm0_255:$imm8),
             (tCMPi8  tGPR:$Rn, imm0_255:$imm8)>;
 def : T1Pat<(ARMcmpZ tGPR:$Rn, tGPR:$Rm),
             (tCMPr   tGPR:$Rn, tGPR:$Rm)>;
 
-// Subtract with carry
-def : T1Pat<(ARMaddc tGPR:$lhs, imm0_7_neg:$rhs),
-            (tSUBSi3 tGPR:$lhs, imm0_7_neg:$rhs)>;
-def : T1Pat<(ARMaddc tGPR:$lhs, imm8_255_neg:$rhs),
-            (tSUBSi8 tGPR:$lhs, imm8_255_neg:$rhs)>;
-
 // Bswap 16 with load/store
 def : T1Pat<(srl (bswap (extloadi16 t_addrmode_is2:$addr)), (i32 16)),
             (tREV16 (tLDRHi t_addrmode_is2:$addr))>;
 def : T1Pat<(srl (bswap (extloadi16 t_addrmode_rr:$addr)), (i32 16)),
             (tREV16 (tLDRHr t_addrmode_rr:$addr))>;
 def : T1Pat<(truncstorei16 (srl (bswap tGPR:$Rn), (i32 16)),
                            t_addrmode_is2:$addr),
             (tSTRHi(tREV16 tGPR:$Rn), t_addrmode_is2:$addr)>;

test/CodeGen/Thumb/long.ll

entry:
         %or = or i64 %shl, 1
         %sub = sub nsw i64 %x, %or
         ret i64 %sub
 ; CHECK-LABEL: f9c:
 ; CHECK: subs r0, r0, #1
 ; CHECK: sbcs r1, r2
 }
 
-define i64 @f9d(i64 %x, i32 %y) { ; SUBS with small negative imm => SUBS reg
-; FIXME: this would be better lowered as an `ADDS imm`
+define i64 @f9d(i64 %x, i32 %y) { ; SUBS with small negative imm => ADDS imm
 entry:
         %conv = sext i32 %y to i64
         %shl = shl i64 %conv, 32
         %or = or i64 %shl, 4294967295
         %sub = sub nsw i64 %x, %or
         ret i64 %sub
 ; CHECK-LABEL: f9d:
-; CHECK: movs r3, #0
-; CHECK: mvns r3, r3
-; CHECK: subs r0, r0, r3
+; CHECK: adds r0, r0, #1
 ; CHECK: sbcs r1, r2
 }
 
 define i64 @f(i32 %a, i32 %b) {
 entry:
         %tmp = sext i32 %a to i64               ; <i64> [#uses=1]
         %tmp1 = sext i32 %b to i64              ; <i64> [#uses=1]
         %tmp2 = mul i64 %tmp1, %tmp             ; <i64> [#uses=1]

 }
 
 define i64 @f11(i64 %x, i64 %y) {
 entry:
         %tmp1 = add i64 -1000, %y
         %tmp2 = add i64 %tmp1, -1000
         ret i64 %tmp2
 ; CHECK-LABEL: f11:
+; CHECK: movs r0, #125
+; CHECK: lsls r0, r0, #3
 ; CHECK: movs r1, #0
-; CHECK: ldr  r0,
-; CHECK: adds r2, r2, r0
+; CHECK: subs r2, r2, r0
 ; CHECK: sbcs r3, r1
-; CHECK: adds r0, r2, r0
+; CHECK: subs r0, r2, r0
 ; CHECK: sbcs r3, r1
 ; CHECK: movs r1, r3
 }