[ARM] Lower "(x<<c) > 0x80000000U" to "lsls" on Thumb1.

[efriedma]

Summary

This is extremely specific, but saves three instructions when it's legal. I don't think the code can be usefully generalized.

Depends on D65175.

[samparker]

LGTM

[ostannard]

Would this also be profitable for Thumb2?

[efriedma]

Would this also be profitable for Thumb2?

I think it saves only one instruction on ARM/Thumb2 ("cmp rN, #0x80000000" is legal). Still worthwhile, I guess, assuming there isn't some sort of performance penalty for branching based on a shift. But I'd also have to figure out the right heuristics for D65175, since the transforms interact, and do a little more implementation work to lower ARMISD::LSLS. I'll leave a FIXME.

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

static const AddSubFlagsOpcodePair AddSubFlagsOpcodeMap[] = {
   {ARM::tADDSrr, ARM::tADDrr},
   {ARM::tADCS, ARM::tADC},
 
   {ARM::tSUBSi3, ARM::tSUBi3},
   {ARM::tSUBSi8, ARM::tSUBi8},
   {ARM::tSUBSrr, ARM::tSUBrr},
   {ARM::tSBCS, ARM::tSBC},
   {ARM::tRSBS, ARM::tRSB},
+  {ARM::tLSLSri, ARM::tLSLri},
 
   {ARM::t2ADDSri, ARM::t2ADDri},
   {ARM::t2ADDSrr, ARM::t2ADDrr},
   {ARM::t2ADDSrs, ARM::t2ADDrs},
 
   {ARM::t2SUBSri, ARM::t2SUBri},
   {ARM::t2SUBSrr, ARM::t2SUBrr},
   {ARM::t2SUBSrs, ARM::t2SUBrs},

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

enum NodeType : unsigned {
       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.
       RRX,          // V = RRX X, Flag     -> srl X, 1 + shift in carry flag.
 
       ADDC,         // Add with carry
       ADDE,         // Add using carry
       SUBC,         // Sub with carry
       SUBE,         // Sub using carry
+      LSLS,         // Shift left producing carry
 
       VMOVRRD,      // double to two gprs.
       VMOVDRR,      // Two gprs to double.
       VMOVSR,       // move gpr to single, used for f32 literal constructed in a gpr
 
       EH_SJLJ_SETJMP,         // SjLj exception handling setjmp.
       EH_SJLJ_LONGJMP,        // SjLj exception handling longjmp.
       EH_SJLJ_SETUP_DISPATCH, // SjLj exception handling setup_dispatch.

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

const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
   case ARMISD::SRL_FLAG:      return "ARMISD::SRL_FLAG";
   case ARMISD::SRA_FLAG:      return "ARMISD::SRA_FLAG";
   case ARMISD::RRX:           return "ARMISD::RRX";
 
   case ARMISD::ADDC:          return "ARMISD::ADDC";
   case ARMISD::ADDE:          return "ARMISD::ADDE";
   case ARMISD::SUBC:          return "ARMISD::SUBC";
   case ARMISD::SUBE:          return "ARMISD::SUBE";
+  case ARMISD::LSLS:          return "ARMISD::LSLS";
 
   case ARMISD::VMOVRRD:       return "ARMISD::VMOVRRD";
   case ARMISD::VMOVDRR:       return "ARMISD::VMOVDRR";
   case ARMISD::VMOVhr:        return "ARMISD::VMOVhr";
   case ARMISD::VMOVrh:        return "ARMISD::VMOVrh";
   case ARMISD::VMOVSR:        return "ARMISD::VMOVSR";
 
   case ARMISD::EH_SJLJ_SETJMP: return "ARMISD::EH_SJLJ_SETJMP";
if (isMask_32(Mask) && (RHSV & ~Mask) == 0 && Mask != 255 && Mask != 65535) {
       unsigned ShiftBits = countLeadingZeros(Mask);
       if (RHSV && (RHSV > 255 || (RHSV << ShiftBits) <= 255)) {
         SDValue ShiftAmt = DAG.getConstant(ShiftBits, dl, MVT::i32);
         LHS = DAG.getNode(ISD::SHL, dl, MVT::i32, LHS.getOperand(0), ShiftAmt);
         RHS = DAG.getConstant(RHSV << ShiftBits, dl, MVT::i32);
       }
     }
   }
+
+  // The specific comparison "(x<<c) > 0x80000000U" can be optimized to a
+  // single "lsls x, c+1".  The shift sets the "C" and "Z" flags the same
+  // way a cmp would.
+  // FIXME: Add support for ARM/Thumb2; this would need isel patterns, and
+  // some tweaks to the heuristics for the previous and->shift transform.
+  // FIXME: Optimize cases where the LHS isn't a shift.
+  if (Subtarget->isThumb1Only() && LHS->getOpcode() == ISD::SHL &&
+      isa<ConstantSDNode>(RHS) &&
+      cast<ConstantSDNode>(RHS)->getZExtValue() == 0x80000000U &&
+      CC == ISD::SETUGT && isa<ConstantSDNode>(LHS.getOperand(1)) &&
+      cast<ConstantSDNode>(LHS.getOperand(1))->getZExtValue() < 31) {
+    unsigned ShiftAmt =
+      cast<ConstantSDNode>(LHS.getOperand(1))->getZExtValue() + 1;
+    SDValue Shift = DAG.getNode(ARMISD::LSLS, dl,
+                                DAG.getVTList(MVT::i32, MVT::i32),
+                                LHS.getOperand(0),
+                                DAG.getConstant(ShiftAmt, dl, MVT::i32));
+    SDValue Chain = DAG.getCopyToReg(DAG.getEntryNode(), dl, ARM::CPSR,
+                                     Shift.getValue(1), SDValue());
+    ARMcc = DAG.getConstant(ARMCC::HI, dl, MVT::i32);
+    return Chain.getValue(1);
+  }
+
   ARMCC::CondCodes CondCode = IntCCToARMCC(CC);
 
   // If the RHS is a constant zero then the V (overflow) flag will never be
   // set. This can allow us to simplify GE to PL or LT to MI, which can be
   // simpler for other passes (like the peephole optimiser) to deal with.
   if (isNullConstant(RHS)) {
     switch (CondCode) {
       default: break;

llvm/trunk/lib/Target/ARM/ARMInstrInfo.td

 
 def ARMsrl_flag      : SDNode<"ARMISD::SRL_FLAG", SDTIntUnaryOp, [SDNPOutGlue]>;
 def ARMsra_flag      : SDNode<"ARMISD::SRA_FLAG", SDTIntUnaryOp, [SDNPOutGlue]>;
 def ARMrrx           : SDNode<"ARMISD::RRX"     , SDTIntUnaryOp, [SDNPInGlue ]>;
 
 def ARMaddc          : SDNode<"ARMISD::ADDC",  SDTBinaryArithWithFlags,
                               [SDNPCommutative]>;
 def ARMsubc          : SDNode<"ARMISD::SUBC",  SDTBinaryArithWithFlags>;
+def ARMlsls          : SDNode<"ARMISD::LSLS",  SDTBinaryArithWithFlags>;
 def ARMadde          : SDNode<"ARMISD::ADDE",  SDTBinaryArithWithFlagsInOut>;
 def ARMsube          : SDNode<"ARMISD::SUBE",  SDTBinaryArithWithFlagsInOut>;
 
 def ARMthread_pointer: SDNode<"ARMISD::THREAD_POINTER", SDT_ARMThreadPointer>;
 def ARMeh_sjlj_setjmp: SDNode<"ARMISD::EH_SJLJ_SETJMP",
                                SDT_ARMEH_SJLJ_Setjmp,
                                [SDNPHasChain, SDNPSideEffect]>;
 def ARMeh_sjlj_longjmp: SDNode<"ARMISD::EH_SJLJ_LONGJMP",

llvm/trunk/lib/Target/ARM/ARMInstrThumb.td

def tSUBSrr : tPseudoInst<(outs tGPR:$Rd), (ins tGPR:$Rn, tGPR:$Rm),
                 Requires<[IsThumb1Only]>,
                 Sched<[WriteALU]>;
 
   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 tLSLSri : tPseudoInst<(outs tGPR:$Rd), (ins tGPR:$Rn, imm0_31:$imm5),
+                            2, IIC_iALUr,
+                            [(set tGPR:$Rd, CPSR, (ARMlsls tGPR:$Rn, imm0_31:$imm5))]>,
+                Requires<[IsThumb1Only]>,
+                Sched<[WriteALU]>;
 }
 
 
 def : T1Pat<(ARMsubs tGPR:$Rn, tGPR:$Rm), (tSUBSrr $Rn, $Rm)>;
 def : T1Pat<(ARMsubs tGPR:$Rn, imm0_7:$imm3), (tSUBSi3 $Rn, imm0_7:$imm3)>;
 def : T1Pat<(ARMsubs tGPR:$Rn, imm0_255:$imm8), (tSUBSi8 $Rn, imm0_255:$imm8)>;
 
 

llvm/trunk/test/CodeGen/Thumb/cmp-and-fold.ll

if.end:
   ret void
 }
 
 define void @test2(i32 %x, void ()* %f)  {
 ; CHECK-LABEL: test2:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r7, lr}
 ; CHECK-NEXT:    push {r7, lr}
-; CHECK-NEXT:    movs r2, #1
-; CHECK-NEXT:    lsls r2, r2, #31
-; CHECK-NEXT:    lsls r0, r0, #7
-; CHECK-NEXT:    cmp r0, r2
+; CHECK-NEXT:    lsls r0, r0, #8
 ; CHECK-NEXT:    bhi .LBB1_2
 ; CHECK-NEXT:  @ %bb.1: @ %if.then
 ; CHECK-NEXT:    blx r1
 ; CHECK-NEXT:  .LBB1_2: @ %if.end
 ; CHECK-NEXT:    pop {r7, pc}
 entry:
   %a = shl i32 %x, 7
   %cmp = icmp ugt i32 %a, 2147483648
   br i1 %cmp, label %if.end, label %if.then
 
 if.then:
   tail call void %f()
   br label %if.end
 
 if.end:
   ret void
 }
 
 define void @test3(i32 %x, void ()* %f)  {
 ; CHECK-LABEL: test3:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    .save {r7, lr}
 ; CHECK-NEXT:    push {r7, lr}
-; CHECK-NEXT:    movs r2, #1
-; CHECK-NEXT:    lsls r2, r2, #31
-; CHECK-NEXT:    lsls r0, r0, #2
-; CHECK-NEXT:    cmp r0, r2
+; CHECK-NEXT:    lsls r0, r0, #3
 ; CHECK-NEXT:    bhi .LBB2_2
 ; CHECK-NEXT:  @ %bb.1: @ %if.then
 ; CHECK-NEXT:    blx r1
 ; CHECK-NEXT:  .LBB2_2: @ %if.end
 ; CHECK-NEXT:    pop {r7, pc}
 entry:
   %a = and i32 %x, 1073741823
   %cmp = icmp ugt i32 %a, 536870912