ARM: avoid infinite combining loop

[t.p.northover]

Summary

One of the transformations done by PerformCMOVCombine increases DAG complexity so that one of the output values can be shared with the compare operation (written as a SUBS). Since this is the reverse of normal combining, it can be collapsed back later in the worklist, leading to an infinite loop.

I think there was a little existing logic to avoid this (the LHS != RHS check) , but it's fragile and nowhere near covers all possible combines; I could not extend it satisfactorily to cover this case and others.

So this patch changes the inserted ISD::SUB into a new ARMISD::OpaqueSUB with the same semantics but that doesn't undergo combining to avoid the problem.

[t.p.northover]

Ping.

[kristof.beyls]

I guess you're mainly asking review on this to get opinions on the approach to introduce new pseudo instructions just to avoid cycles during DAG combining and/or lowering?
From the patch, I furthermore guess that introducing a new pseudo leads to quite a bit of code duplication/violations of the "don't-repeat-yourself" principle in the instruction matching patterns?

With that, I wonder:

• It seems unlikely this is the only place where a problem with cycles during DAG combining/lowering pops up.
  • If it is the only place: what is so exceptional here that this really is the only place?
  • If it is not: what are the other approaches already taken elsewhere to avoid cycles? Why are alternative approaches not applicable here (or why are they an even worse solution)? Is there actually some guidance written up somewhere on which approaches exist and which to take to avoid cycles?
• Instead of producing a whole new pseudo, I guess an alternative would be to introduce a way to flag on ISD nodes "do not combine this node any further" as a more generic mechanism. I guess for that to work, some bit somewhere on the ISD node would be needed to store that info. I wonder if you considered such an approach too? I guess it has the advantage that it doesn't require violating the DRY principle in the instruction patterns?

[t.p.northover]

It seems unlikely this is the only place where a problem with cycles during DAG combining/lowering pops up.

I think it's pretty rare. Mostly combines genuinely do simplify the DAG, or replace the lot with a target node. I did consider the latter but decided getting equivalent CodeGen out of it would be just as bad as (or worse than) the duplicated patterns for the subtraction.

I guess an alternative would be to introduce a way to flag on ISD nodes "do not combine this node any further" as a more generic mechanism. I guess for that to work, some bit somewhere on the ISD node would be needed to store that info.

I hadn't considered an approach like that, but I think obeying such a flag would be pretty difficult. You don't just have to check the root of a combine, but every node involved. That probably means checks throughout the DAGCombiner.

[samparker]

I thought the normal way to stop combining was to return the original node. Could you not manually replace N with Res and then return N?

[efriedma]

I thought the normal way to stop combining was to return the original node. Could you not manually replace N with Res and then return N?

You can sort of hide the new node from the worklist, but it's not usually a good idea: if the node gets back on the worklist some other way, you can end up with an infinite combining loop. The goal should be a "stable" DAG, which DAGCombine won't modify further.

[samparker]

Ok, fair point. If we are going to introduce a new node to fix this issue, could we have a SUBS node that can be glued to the CMOV?

[t.p.northover]

Ok, fair point. If we are going to introduce a new node to fix this issue, could we have a SUBS node that can be glued to the CMOV?

I believe later passes already tidy things up enough that we don't need to embellish the DAG phase. For example if I compile:

define i32 @foo(i32 %lhs, i32 %rhs, i32 %in) {
  %tst = icmp eq i32 %lhs, %rhs
  %res = select i1 %tst, i32 0, i32 %in
  ret i32 %res
}

with this patch, I still get the optimum CodeGen of a single cmp and cmov.

[t.p.northover]

Ping.

[samparker]

My point was that, even though this extra work and as you mentioned in the comments, the test case isn't generating optimum code. We could introduce a subs node to remove the unnecessary cmp, making the sub opaque and improving codegen. Unless there's a reason why we couldn't do this?

[t.p.northover]

Ah, I see what you mean. It's not pretty, but this updated patch seems to do the trick.

[samparker]

Great to see those other test changes! LGTM with the few minor comments, no need to re-review. cheers!

llvm/lib/Target/ARM/ARMISelLowering.h

88

Maybe just SUBS now? And with an updated comment.

llvm/lib/Target/ARM/ARMInstrInfo.td

3631

whitespace.

llvm/lib/Target/ARM/ARMInstrThumb.td

1285

whitespace.

llvm/lib/Target/ARM/ARMInstrThumb2.td

2084

whitespace.

[t.p.northover]

Great to see those other test changes!

Yes, definitely a pleasant surprise. Thanks for the reviews; I've committed it with your suggested changes as r348122.

llvm/lib/Target/ARM/ARMISelLowering.h

enum NodeType : unsigned {
       CMP,          // ARM compare instructions.
       CMN,          // ARM CMN instructions.
       CMPZ,         // ARM compare that sets only Z flag.
       CMPFP,        // ARM VFP compare instruction, sets FPSCR.
       CMPFPw0,      // ARM VFP compare against zero instruction, sets FPSCR.
       FMSTAT,       // ARM fmstat instruction.
 
       CMOV,         // ARM conditional move instructions.
+      OpaqueSUBS,   // Subtract that DAG combiner should ignore.
 
       SSAT,         // Signed saturation
       USAT,         // Unsigned saturation
 
       BCC_i64,
 
       SRL_FLAG,     // V,Flag = srl_flag X -> srl X, 1 + save carry out.
       SRA_FLAG,     // V,Flag = sra_flag X -> sra X, 1 + save carry out.

llvm/lib/Target/ARM/ARMISelLowering.cpp

const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
   case ARMISD::CMN:           return "ARMISD::CMN";
   case ARMISD::CMPZ:          return "ARMISD::CMPZ";
   case ARMISD::CMPFP:         return "ARMISD::CMPFP";
   case ARMISD::CMPFPw0:       return "ARMISD::CMPFPw0";
   case ARMISD::BCC_i64:       return "ARMISD::BCC_i64";
   case ARMISD::FMSTAT:        return "ARMISD::FMSTAT";
 
   case ARMISD::CMOV:          return "ARMISD::CMOV";
+  case ARMISD::OpaqueSUBS:    return "ARMISD::OpaqueSUBS";
 
   case ARMISD::SSAT:          return "ARMISD::SSAT";
   case ARMISD::USAT:          return "ARMISD::USAT";
 
   case ARMISD::SRL_FLAG:      return "ARMISD::SRL_FLAG";
   case ARMISD::SRA_FLAG:      return "ARMISD::SRA_FLAG";
   case ARMISD::RRX:           return "ARMISD::RRX";
 
if (CC == ARMCC::EQ && isOneConstant(TrueVal)) {
         SDValue Neg = DAG.getNode(ISD::USUBO, dl, VTs, FalseVal, Sub);
         // ISD::SUBCARRY returns a borrow but we want the carry here
         // actually.
         SDValue Carry =
             DAG.getNode(ISD::SUB, dl, MVT::i32,
                         DAG.getConstant(1, dl, MVT::i32), Neg.getValue(1));
         Res = DAG.getNode(ISD::ADDCARRY, dl, VTs, Sub, Neg, Carry);
       }
-    } else if (CC == ARMCC::NE && LHS != RHS &&
+    } else if (CC == ARMCC::NE && !isNullConstant(RHS) &&
                (!Subtarget->isThumb1Only() || isPowerOf2Constant(TrueVal))) {
       // This seems pointless but will allow us to combine it further below.
-      // CMOV 0, z, !=, (CMPZ x, y) -> CMOV (SUB x, y), z, !=, (CMPZ x, y)
-      SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, LHS, RHS);
+      // CMOV 0, z, !=, (CMPZ x, y) -> CMOV (SUBS x, y), z, !=, (SUBS x, y):1
+      SDValue Sub = DAG.getNode(ARMISD::OpaqueSUBS, dl,
+                                DAG.getVTList(VT, MVT::i32), LHS, RHS);
+      SDValue CPSRGlue = DAG.getCopyToReg(DAG.getEntryNode(), dl, ARM::CPSR,
+                                          Sub.getValue(1), SDValue());
       Res = DAG.getNode(ARMISD::CMOV, dl, VT, Sub, TrueVal, ARMcc,
-                        N->getOperand(3), Cmp);
+                        N->getOperand(3), CPSRGlue.getValue(1));
+      FalseVal = Sub;
     }
   } else if (isNullConstant(TrueVal)) {
-    if (CC == ARMCC::EQ && LHS != RHS &&
+    if (CC == ARMCC::EQ && !isNullConstant(RHS) &&
         (!Subtarget->isThumb1Only() || isPowerOf2Constant(FalseVal))) {
       // This seems pointless but will allow us to combine it further below
       // Note that we change == for != as this is the dual for the case above.
-      // CMOV z, 0, ==, (CMPZ x, y) -> CMOV (SUB x, y), z, !=, (CMPZ x, y)
-      SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, LHS, RHS);
+      // CMOV z, 0, ==, (CMPZ x, y) -> CMOV (SUBS x, y), z, !=, (SUBS x, y):1
+      SDValue Sub = DAG.getNode(ARMISD::OpaqueSUBS, dl,
+                                DAG.getVTList(VT, MVT::i32), LHS, RHS);
+      SDValue CPSRGlue = DAG.getCopyToReg(DAG.getEntryNode(), dl, ARM::CPSR,
+                                          Sub.getValue(1), SDValue());
       Res = DAG.getNode(ARMISD::CMOV, dl, VT, Sub, FalseVal,
                         DAG.getConstant(ARMCC::NE, dl, MVT::i32),
-                        N->getOperand(3), Cmp);
+                        N->getOperand(3), CPSRGlue.getValue(1));
+      FalseVal = Sub;
     }
   }
 
   // On Thumb1, the DAG above may be further combined if z is a power of 2
   // (z == 2 ^ K).
-  // CMOV (SUB x, y), z, !=, (CMPZ x, y) ->
+  // CMOV (SUBS x, y), z, !=, (SUBS x, y):1 ->
   //       merge t3, t4
   // where t1 = (SUBCARRY (SUB x, y), z, 0)
   //       t2 = (SUBCARRY (SUB x, y), t1:0, t1:1)
   //       t3 = if K != 0 then (SHL t2:0, K) else t2:0
   //       t4 = (SUB 1, t2:1)   [ we want a carry, not a borrow ]
   const APInt *TrueConst;
   if (Subtarget->isThumb1Only() && CC == ARMCC::NE &&
-      (FalseVal.getOpcode() == ISD::SUB) && (FalseVal.getOperand(0) == LHS) &&
-      (FalseVal.getOperand(1) == RHS) &&
+      (FalseVal.getOpcode() == ARMISD::OpaqueSUBS) &&
+      (FalseVal.getOperand(0) == LHS) && (FalseVal.getOperand(1) == RHS) &&
       (TrueConst = isPowerOf2Constant(TrueVal))) {
     SDVTList VTs = DAG.getVTList(VT, MVT::i32);
     unsigned ShiftAmount = TrueConst->logBase2();
     if (ShiftAmount)
       TrueVal = DAG.getConstant(1, dl, VT);
     SDValue Subc = DAG.getNode(ISD::USUBO, dl, VTs, FalseVal, TrueVal);
     Res = DAG.getNode(ISD::SUBCARRY, dl, VTs, FalseVal, Subc, Subc.getValue(1));
     // Make it a carry, not a borrow.

llvm/lib/Target/ARM/ARMInstrInfo.td

def ARMcall_nolink   : SDNode<"ARMISD::CALL_NOLINK", SDT_ARMcall,
                                SDNPVariadic]>;
 
 def ARMretflag       : SDNode<"ARMISD::RET_FLAG", SDTNone,
                               [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;
 def ARMintretflag    : SDNode<"ARMISD::INTRET_FLAG", SDT_ARMcall,
                               [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;
 def ARMcmov          : SDNode<"ARMISD::CMOV", SDT_ARMCMov,
                               [SDNPInGlue]>;
+def ARMopaquesub     : SDNode<"ARMISD::OpaqueSUBS", SDTIntBinOp, [SDNPOutGlue]>;
 
 def ARMssatnoshift   : SDNode<"ARMISD::SSAT", SDTIntSatNoShOp, []>;
 
 def ARMusatnoshift   : SDNode<"ARMISD::USAT", SDTIntSatNoShOp, []>;
 
 def ARMbrcond        : SDNode<"ARMISD::BRCOND", SDT_ARMBrcond,
                               [SDNPHasChain, SDNPInGlue, SDNPOutGlue]>;
 

 //
 
 let isAdd = 1 in
 defm ADD  : AsI1_bin_irs<0b0100, "add",
                          IIC_iALUi, IIC_iALUr, IIC_iALUsr, add, 1>;
 defm SUB  : AsI1_bin_irs<0b0010, "sub",
                          IIC_iALUi, IIC_iALUr, IIC_iALUsr, sub>;
 
+
 // ADD and SUB with 's' bit set.
 //
 // Currently, ADDS/SUBS are pseudo opcodes that exist only in the
 // selection DAG. They are "lowered" to real ADD/SUB opcodes by
 // AdjustInstrPostInstrSelection where we determine whether or not to
 // set the "s" bit based on CPSR liveness.
 //
 // FIXME: Eliminate ADDS/SUBS pseudo opcodes after adding tablegen
 // support for an optional CPSR definition that corresponds to the DAG
 // node's second value. We can then eliminate the implicit def of CPSR.
 let isAdd = 1 in
 defm ADDS : AsI1_bin_s_irs<IIC_iALUi, IIC_iALUr, IIC_iALUsr, ARMaddc, 1>;
 defm SUBS : AsI1_bin_s_irs<IIC_iALUi, IIC_iALUr, IIC_iALUsr, ARMsubc>;
 
+def : ARMPat<(ARMopaquesub GPR:$Rn, mod_imm:$imm), (SUBSri $Rn, mod_imm:$imm)>;
+def : ARMPat<(ARMopaquesub GPR:$Rn, GPR:$Rm), (SUBSrr $Rn, $Rm)>;
+def : ARMPat<(ARMopaquesub GPR:$Rn, so_reg_imm:$shift),
+             (SUBSrsi $Rn, so_reg_imm:$shift)>;
+def : ARMPat<(ARMopaquesub GPR:$Rn, so_reg_reg:$shift),
+             (SUBSrsr $Rn, so_reg_reg:$shift)>;
+
+
 let isAdd = 1 in
 defm ADC : AI1_adde_sube_irs<0b0101, "adc", ARMadde, 1>;
 defm SBC : AI1_adde_sube_irs<0b0110, "sbc", ARMsube>;
 
 defm RSB  : AsI1_rbin_irs<0b0011, "rsb",
                           IIC_iALUi, IIC_iALUr, IIC_iALUsr,
                           sub>;
 

llvm/lib/Target/ARM/ARMInstrThumb.td

def tSUBi3 :                    // A8.6.210 T1
   T1sIGenEncodeImm<0b01111, (outs tGPR:$Rd), (ins tGPR:$Rm, imm0_7:$imm3),
                    IIC_iALUi,
                    "sub", "\t$Rd, $Rm, $imm3",
                    [(set tGPR:$Rd, (add tGPR:$Rm, imm0_7_neg:$imm3))]>,
                    Sched<[WriteALU]> {
   bits<3> imm3;
   let Inst{8-6} = imm3;
 }
-
 def tSUBi8 :                    // A8.6.210 T2
   T1sItGenEncodeImm<{1,1,1,?,?}, (outs tGPR:$Rdn),
                     (ins tGPR:$Rn, imm0_255:$imm8), IIC_iALUi,
                     "sub", "\t$Rdn, $imm8",
                     [(set tGPR:$Rdn, (add tGPR:$Rn, imm8_255_neg:$imm8))]>,
                     Sched<[WriteALU]>;
 
 def : tInstSubst<"add${s}${p} $rd, $rn, $imm",
let hasPostISelHook = 1, Defs = [CPSR] in {
 
   def tRSBS   : tPseudoInst<(outs tGPR:$Rd), (ins tGPR:$Rn),
                             2, IIC_iALUr,
                             [(set tGPR:$Rd, CPSR, (ARMsubc 0, tGPR:$Rn))]>,
                 Requires<[IsThumb1Only]>,
                 Sched<[WriteALU]>;
 }
 
+
+def : T1Pat<(ARMopaquesub tGPR:$Rn, tGPR:$Rm), (tSUBSrr $Rn, $Rm)>;
+def : T1Pat<(ARMopaquesub tGPR:$Rn, imm0_7:$imm3),
+            (tSUBSi3 $Rn, imm0_7:$imm3)>;
+def : T1Pat<(ARMopaquesub tGPR:$Rn, imm0_255:$imm8),
+            (tSUBSi8 $Rn, imm0_255:$imm8)>;
+
+
 // Sign-extend byte
 def tSXTB :                     // A8.6.222
   T1pIMiscEncode<{0,0,1,0,0,1,?}, (outs tGPR:$Rd), (ins tGPR:$Rm),
                  IIC_iUNAr,
                  "sxtb", "\t$Rd, $Rm",
                  [(set tGPR:$Rd, (sext_inreg tGPR:$Rm, i8))]>,
                  Requires<[IsThumb, IsThumb1Only, HasV6]>,
                  Sched<[WriteALU]>;

llvm/lib/Target/ARM/ARMInstrThumb2.td

 //===----------------------------------------------------------------------===//
 //  Arithmetic Instructions.
 //
 
 let isAdd = 1 in
 defm t2ADD  : T2I_bin_ii12rs<0b000, "add", add, 1>;
 defm t2SUB  : T2I_bin_ii12rs<0b101, "sub", sub>;
 
+
 // ADD and SUB with 's' bit set. No 12-bit immediate (T4) variants.
 //
 // Currently, t2ADDS/t2SUBS are pseudo opcodes that exist only in the
 // selection DAG. They are "lowered" to real t2ADD/t2SUB opcodes by
 // AdjustInstrPostInstrSelection where we determine whether or not to
 // set the "s" bit based on CPSR liveness.
 //
 // FIXME: Eliminate t2ADDS/t2SUBS pseudo opcodes after adding tablegen
 // support for an optional CPSR definition that corresponds to the DAG
 // node's second value. We can then eliminate the implicit def of CPSR.
 defm t2ADDS : T2I_bin_s_irs <IIC_iALUi, IIC_iALUr, IIC_iALUsi, ARMaddc, 1>;
 defm t2SUBS : T2I_bin_s_irs <IIC_iALUi, IIC_iALUr, IIC_iALUsi, ARMsubc>;
 
+def : T2Pat<(ARMopaquesub GPRnopc:$Rn, t2_so_imm:$imm),
+            (t2SUBSri $Rn, t2_so_imm:$imm)>;
+def : T2Pat<(ARMopaquesub GPRnopc:$Rn, rGPR:$Rm), (t2SUBSrr $Rn, $Rm)>;
+def : T2Pat<(ARMopaquesub GPRnopc:$Rn, t2_so_reg:$ShiftedRm),
+            (t2SUBSrs $Rn, t2_so_reg:$ShiftedRm)>;
+
 let hasPostISelHook = 1 in {
 defm t2ADC  : T2I_adde_sube_irs<0b1010, "adc", ARMadde, 1>;
 defm t2SBC  : T2I_adde_sube_irs<0b1011, "sbc", ARMsube>;
 }
 
 def : t2InstSubst<"adc${s}${p} $rd, $rn, $imm",
                  (t2SBCri rGPR:$rd, rGPR:$rn, t2_so_imm_not:$imm, pred:$p, s_cc_out:$s)>;
 def : t2InstSubst<"sbc${s}${p} $rd, $rn, $imm",

llvm/test/CodeGen/ARM/CGP/arm-cgp-casts.ll

entry:
   %conv2 = sext i16 %1 to i32
   %cmp = icmp eq i32 %conv1, %conv2
   %conv3 = zext i1 %cmp to i32
   ret i32 %conv3
 }
 
 ; CHECK-COMMON-LABEL: or_icmp_ugt:
 ; CHECK-COMMON:     ldrb
-; CHECK-COMMON:     sub.w
-; CHECK-COMMON-NOT: uxt
-; CHECK-COMMON:     cmp.w
+; CHECK-COMMON:     subs.w
 ; CHECK-COMMON-NOT: uxt
 ; CHECK-COMMON:     cmp
 define i1 @or_icmp_ugt(i32 %arg, i8* %ptr) {
 entry:
   %0 = load i8, i8* %ptr
   %1 = zext i8 %0 to i32
   %mul = shl nuw nsw i32 %1, 1
   %add0 = add nuw nsw i32 %mul, 6

llvm/test/CodeGen/ARM/cmp.ll

 ; CHECK-T2: lsrs    r0, r0, #5
     %tmp = shl i32 %b, 5
     %tmp1 = icmp eq i32 %a, %tmp
     ret i1 %tmp1
 }
 
 define i1 @f7(i32 %a, i32 %b) {
 ; CHECK-LABEL: f7:
-; CHECK: sub     r2, r0, r1, lsr #6
-; CHECK: cmp     r0, r1, lsr #6
-; CHECK: movwne  r2, #1
-; CHECK: mov     r0, r2
-; CHECK-T2: sub.w   r2, r0, r1, lsr #6
-; CHECK-T2: cmp.w   r0, r1, lsr #6
+; CHECK: subs    r0, r0, r1, lsr #6
+; CHECK: movwne  r0, #1
+; CHECK-T2: subs.w   r0, r0, r1, lsr #6
 ; CHECK-T2: it      ne
-; CHECK-T2: movne   r2, #1
-; CHECK-T2: mov     r0, r2
+; CHECK-T2: movne   r0, #1
     %tmp = lshr i32 %b, 6
     %tmp1 = icmp ne i32 %a, %tmp
     ret i1 %tmp1
 }
 
 define i1 @f8(i32 %a, i32 %b) {
 ; CHECK-LABEL: f8:
 ; CHECK: sub     r0, r0, r1, asr #7
 ; CHECK: clz     r0, r0
 ; CHECK: lsr     r0, r0, #5
 ; CHECK-T2: sub.w   r0, r0, r1, asr #7
 ; CHECK-T2: clz     r0, r0
 ; CHECK-T2: lsrs    r0, r0, #5
     %tmp = ashr i32 %b, 7
     %tmp1 = icmp eq i32 %a, %tmp
     ret i1 %tmp1
 }
 
 define i1 @f9(i32 %a) {
 ; CHECK-LABEL: f9:
-; CHECK: sub     r1, r0, r0, ror #8
-; CHECK: cmp     r0, r0, ror #8
-; CHECK: movwne  r1, #1
-; CHECK: mov     r0, r1
-; CHECK-T2: sub.w   r1, r0, r0, ror #8
-; CHECK-T2: cmp.w   r0, r0, ror #8
+; CHECK: subs    r0, r0, r0, ror #8
+; CHECK: movwne  r0, #1
+; CHECK-T2: subs.w   r0, r0, r0, ror #8
 ; CHECK-T2: it      ne
-; CHECK-T2: movne   r1, #1
-; CHECK-T2: mov     r0, r1
+; CHECK-T2: movne   r0, #1
     %l8 = shl i32 %a, 24
     %r8 = lshr i32 %a, 8
     %tmp = or i32 %l8, %r8
     %tmp1 = icmp ne i32 %a, %tmp
     ret i1 %tmp1
 }
 
 ; CHECK-LABEL: swap_cmp_shl

llvm/test/CodeGen/ARM/select.ll

 ; CHECK-LABEL: f12:
 define float @f12(i32 %a, i32 %b) nounwind uwtable readnone ssp {
 ; CHECK-NOT: floatunsisf
   %1 = icmp eq i32 %a, %b
   %2 = uitofp i1 %1 to float
   ret float %2
 }
 
+; CHECK-LABEL: test_overflow_recombine:
+define i1 @test_overflow_recombine(i32 %in) {
+; CHECK: smull [[LO:r[0-9]+]], [[HI:r[0-9]+]]
+; CHECK: subs [[ZERO:r[0-9]+]], [[HI]], [[LO]], asr #31
+; CHECK: movne [[ZERO]], #1
+  %prod = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 0, i32 %in)
+  %overflow = extractvalue { i32, i1 } %prod, 1
+  ret i1 %overflow
+}
+
+declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32)