[Thumb] Add support for tMUL in the compare instruction peephole optimizer

[SjoerdMeijer]

Summary

We also want to optimise tests like this: return a*b == 0. The MULS instruction is flag setting, so we don't need the CMP instruction but can instead branch on the result of the MULS. The generated instructions sequence for this example was: MULS, MOVS, MOVS, CMP. The MOVS instruction load the boolean values resulting from the select instruction, but these MOVS instructions are flag setting and were thus preventing this optimisation. Now we first reorder and move the MULS to before the CMP and generate sequence MOVS, MOVS, MULS, CMP so that the optimisation could still be triggered. Reordering of the MULS and MOVS is safe to do because the subsequent MOVS instructions just set the CPSR register and don't use it, i.e. the CPSR is dead.

[rovka]

Hi Sjoerd,

I'm not sure this is the best way to go, it looks a bit hacky. Why are we generating MOVS for those constants in the first place? It feels like MOV should do the job just as well, and wouldn't touch the flags.

Cheers,
Diana

test/CodeGen/ARM/mul-cmp-peephole.ll

1

I think this would work better as a .mir test (use -stop-before=peephole-opt).

28

Is all this alloca clutter relevant to the test?

[SjoerdMeijer]

Hi Diana,

Thanks a lot for the review! We are generating these constants and moves for an expression like "return A*B == C", where A and B are variables and C is a constant, because this is lowered involving a select_cc is generated. For example:

%mul = mul nsw i32 %b, %a
%cmp = icmp eq i32 %mul, 0
%conv = zext i1 %cmp to i32
ret i32 %conv

this IR gets instruction selected to:

t5: i32 = mul t4, t2

    t19: glue = ARMISD::CMPZ t5, Constant:i32<0>
  t20: i32 = ARMISD::CMOV Constant:i32<0>, Constant:i32<1>, Constant:i32<0>, Register:i32 %CPSR, t19
t11: ch,glue = CopyToReg t0, Register:i32 %R0, t20
t12: ch = ARMISD::RET_FLAG t11, Register:i32 %R0, t11:1

and then we end up with these MIs:

%vreg2<def,tied3>, %CPSR<def> = tMUL %vreg1, %vreg0<tied0>, pred:14, pred:%noreg; tGPR:%vreg2,%vreg1,%vreg0

%vreg3<def>, %CPSR<def> = tMOVi8 1, pred:14, pred:%noreg; tGPR:%vreg3
%vreg4<def>, %CPSR<def> = tMOVi8 0, pred:14, pred:%noreg; tGPR:%vreg4
tCMPi8 %vreg2<kill>, 0, pred:14, pred:%noreg, %CPSR<imp-def>; tGPR:%vreg2
%vreg5<def> = tMOVCCr_pseudo %vreg4<kill>, %vreg3<kill>, pred:0, pred:%CPSR; tGPR:%vreg5,%vreg4,%vreg3
%R0<def> = COPY %vreg5; tGPR:%vreg5
tBX_RET

And the issue is that the move immediate instruction for Thumb1 (V6M) updates the condition flags.

The elegant solution would be a bit of (early) CFG restructuring and 2 exit blocks return the true/false conditions, so that we end up with something similar to this:

MULS     r0,r1,r0
BEQ      |L0.8|
MOVS     r0,#0
BX       lr

L0.8

MOVS     r0,#1
BX       lr

But to achieve that at this point is difficult, hence my solution to simply reorder the constants and the operation.

[rovka]

Right, sorry, I was thinking about Thumb2, where MOV doesn't touch the flags.

I guess reordering isn't so bad in this case, but it will affect the registers that you have available. Before, if the operands for tMUL weren't needed elsewhere you could reuse their registers for the constants, now you might need extra regs for them. E.g. in the first example from the test, you end up using up to r3 instead of just up to r2. I think it would be useful to run some benchmarks with this change, to make sure we're not causing trouble in more complicated cases.

Thanks.

[SjoerdMeijer]

Thanks for the suggestion and I will look into possible correctness issues a bit more, which was also on my todo list. I.e., I ran testing and that didn't show problems for lnt, dhrystone, coremark, eembc, geekbench, spec2k, but spec2k6 might have found something but need to check if that is noise or not.

[SjoerdMeijer]

I have verified correctness and this patch does not show any problems in regression tests or benchmarks. This peephole works on the vregs, so is still in SSA form. As a consequence, the movs won't redefine/kill the MUL operands which would make this reordering illegal. I have added an extra check though that the movs are not predicated. I have also changed the tests into .mir tests (and simplified the 2nd test).

[rovka]

lib/Target/ARM/ARMBaseInstrInfo.cpp

2528

Typo: MOVS instructions (also on line 2531)

2537

Nitpick: I think CanReorder is a better name.

2541

Why not isPredicated?

2541

You should cover this in the tests (i.e. check that the optimization is not performed for a predicated MOV).

test/CodeGen/ARM/cmp1-peephole-thumb.mir

3 ↗

(On Diff #83042)

Nitpick: I'd move this closer to the MIR code. Plus, since the code is dealing with reordering, it's probably a good idea to also check for what you're expecting to see in the output (i.e. the MOVs followed by the MUL).

[SjoerdMeijer]

Thanks for reviewing again. I have fixed the typos in the comments, changed the variable name, and modified the test case. Regarding the predicated MOVs I have taken a slightly different approach. Since we only want to do this peephole optimisation for Thumb1, I first check that the instruction is actually a Thumb1 instruction. And because Thumb1 does not have conditional movs, we can safely omit the isPredicated check (testing shows no issues).

[rovka]

LGTM with a couple more nitpicks (you don't have to upload a new version here, just make the changes and commit).

lib/Target/ARM/ARMBaseInstrInfo.cpp

2534

Another typo: eliminate :D

test/CodeGen/ARM/cmp2-peephole-thumb.mir

8 ↗

(On Diff #84559)

Please move this closer to the MIR code (as you did for the other test), and also check for the compare.

[SjoerdMeijer]

Thanks! Have fixed that, and will commit.

lib/Target/ARM/ARMBaseInstrInfo.cpp

if ((CmpI->getOpcode() == ARM::CMPri ||
       (OI->getOpcode() == ARM::SUBri ||
        OI->getOpcode() == ARM::t2SUBri) &&
       OI->getOperand(1).getReg() == SrcReg &&
       OI->getOperand(2).getImm() == ImmValue)
     return true;
   return false;
 }
 
+static bool isOptimizeCompareCandidate(MachineInstr *MI, bool &IsThumb1) {
+  switch (MI->getOpcode()) {
+  default: return false;
+  case ARM::tLSLri:
+  case ARM::tLSRri:
+  case ARM::tLSLrr:
+  case ARM::tLSRrr:
+  case ARM::tSUBrr:
+  case ARM::tADDrr:
+  case ARM::tADDi3:
+  case ARM::tADDi8:
+  case ARM::tSUBi3:
+  case ARM::tSUBi8:
+  case ARM::tMUL:
+    IsThumb1 = true;
+    LLVM_FALLTHROUGH;
+  case ARM::RSBrr:
+  case ARM::RSBri:
+  case ARM::RSCrr:
+  case ARM::RSCri:
+  case ARM::ADDrr:
+  case ARM::ADDri:
+  case ARM::ADCrr:
+  case ARM::ADCri:
+  case ARM::SUBrr:
+  case ARM::SUBri:
+  case ARM::SBCrr:
+  case ARM::SBCri:
+  case ARM::t2RSBri:
+  case ARM::t2ADDrr:
+  case ARM::t2ADDri:
+  case ARM::t2ADCrr:
+  case ARM::t2ADCri:
+  case ARM::t2SUBrr:
+  case ARM::t2SUBri:
+  case ARM::t2SBCrr:
+  case ARM::t2SBCri:
+  case ARM::ANDrr:
+  case ARM::ANDri:
+  case ARM::t2ANDrr:
+  case ARM::t2ANDri:
+  case ARM::ORRrr:
+  case ARM::ORRri:
+  case ARM::t2ORRrr:
+  case ARM::t2ORRri:
+  case ARM::EORrr:
+  case ARM::EORri:
+  case ARM::t2EORrr:
+  case ARM::t2EORri:
+  case ARM::t2LSRri:
+  case ARM::t2LSRrr:
+  case ARM::t2LSLri:
+  case ARM::t2LSLrr:
+    return true;
+  }
+}
+
 /// optimizeCompareInstr - Convert the instruction supplying the argument to the
 /// comparison into one that sets the zero bit in the flags register;
 /// Remove a redundant Compare instruction if an earlier instruction can set the
 /// flags in the same way as Compare.
 /// E.g. SUBrr(r1,r2) and CMPrr(r1,r2). We also handle the case where two
 /// operands are swapped: SUBrr(r1,r2) and CMPrr(r2,r1), by updating the
 /// condition code of instructions which use the flags.
 bool ARMBaseInstrInfo::optimizeCompareInstr(
else if (MI->getParent() != CmpInstr.getParent() || CmpValue != 0) {
     // Thus we cannot return here.
     if (CmpInstr.getOpcode() == ARM::CMPri ||
         CmpInstr.getOpcode() == ARM::t2CMPri)
       MI = nullptr;
     else
       return false;
   }
 
+  bool IsThumb1 = false;
+  if (MI && !isOptimizeCompareCandidate(MI, IsThumb1))
+    return false;
+
+  // We also want to do this peephole for cases like this: if (a*b == 0),
+  // and optimise away the CMP instruction from the generated code sequence:
+  // MULS, MOVS, MOVS, CMP. Here the MOVS instruction load the boolean values
+  // resulting from the select instruction, but these MOVS instructions are
+  // flag setting and are thus preventing this optimisation. However, if we
+  // only have MOVS instruction in between the CMP and the other instruction
+  // (the MULS in this example), then the CPSR is dead so we can safely reorder
+  // the sequence into: MOVS, MOVS, MULS, CMP. So we do this reordering, and
+  // then continue the analysis hoping we can eleminate the CMP.
+  if (MI) {
+    --I;
+    bool OnlyMOVS = true;
+    bool HasStmtsInBetween = I != E;
+    for (; I != E; --I) {
+      if(I->getOpcode() != ARM::tMOVi8) {
+        OnlyMOVS = false;
+        break;
+      }
+    }
+    if (HasStmtsInBetween && OnlyMOVS) {
+      MI = MI->removeFromParent();
+      E = CmpInstr;
+      CmpInstr.getParent()->insert(E, MI);
+    }
+    I = CmpInstr;
+    E = MI;
+  }
+
   // Check that CPSR isn't set between the comparison instruction and the one we
   // want to change. At the same time, search for Sub.
   const TargetRegisterInfo *TRI = &getRegisterInfo();
   --I;
   for (; I != E; --I) {
     const MachineInstr &Instr = *I;
 
     if (Instr.modifiesRegister(ARM::CPSR, TRI) ||
bool ARMBaseInstrInfo::optimizeCompareInstr(
 
   // The single candidate is called MI.
   if (!MI) MI = Sub;
 
   // We can't use a predicated instruction - it doesn't always write the flags.
   if (isPredicated(*MI))
     return false;
 
-  bool IsThumb1 = false;
-  switch (MI->getOpcode()) {
-  default: break;
-  case ARM::tLSLri:
-  case ARM::tLSRri:
-  case ARM::tLSLrr:
-  case ARM::tLSRrr:
-  case ARM::tSUBrr:
-  case ARM::tADDrr:
-  case ARM::tADDi3:
-  case ARM::tADDi8:
-  case ARM::tSUBi3:
-  case ARM::tSUBi8:
-    IsThumb1 = true;
-    LLVM_FALLTHROUGH;
-  case ARM::RSBrr:
-  case ARM::RSBri:
-  case ARM::RSCrr:
-  case ARM::RSCri:
-  case ARM::ADDrr:
-  case ARM::ADDri:
-  case ARM::ADCrr:
-  case ARM::ADCri:
-  case ARM::SUBrr:
-  case ARM::SUBri:
-  case ARM::SBCrr:
-  case ARM::SBCri:
-  case ARM::t2RSBri:
-  case ARM::t2ADDrr:
-  case ARM::t2ADDri:
-  case ARM::t2ADCrr:
-  case ARM::t2ADCri:
-  case ARM::t2SUBrr:
-  case ARM::t2SUBri:
-  case ARM::t2SBCrr:
-  case ARM::t2SBCri:
-  case ARM::ANDrr:
-  case ARM::ANDri:
-  case ARM::t2ANDrr:
-  case ARM::t2ANDri:
-  case ARM::ORRrr:
-  case ARM::ORRri:
-  case ARM::t2ORRrr:
-  case ARM::t2ORRri:
-  case ARM::EORrr:
-  case ARM::EORri:
-  case ARM::t2EORrr:
-  case ARM::t2EORri:
-  case ARM::t2LSRri:
-  case ARM::t2LSRrr:
-  case ARM::t2LSLri:
-  case ARM::t2LSLrr: {
-    // Scan forward for the use of CPSR
-    // When checking against MI: if it's a conditional code that requires
-    // checking of the V bit or C bit, then this is not safe to do.
-    // It is safe to remove CmpInstr if CPSR is redefined or killed.
-    // If we are done with the basic block, we need to check whether CPSR is
-    // live-out.
-    SmallVector<std::pair<MachineOperand*, ARMCC::CondCodes>, 4>
-        OperandsToUpdate;
-    bool isSafe = false;
-    I = CmpInstr;
-    E = CmpInstr.getParent()->end();
-    while (!isSafe && ++I != E) {
-      const MachineInstr &Instr = *I;
-      for (unsigned IO = 0, EO = Instr.getNumOperands();
-           !isSafe && IO != EO; ++IO) {
-        const MachineOperand &MO = Instr.getOperand(IO);
-        if (MO.isRegMask() && MO.clobbersPhysReg(ARM::CPSR)) {
-          isSafe = true;
-          break;
-        }
-        if (!MO.isReg() || MO.getReg() != ARM::CPSR)
-          continue;
-        if (MO.isDef()) {
-          isSafe = true;
-          break;
-        }
-        // Condition code is after the operand before CPSR except for VSELs.
-        ARMCC::CondCodes CC;
-        bool IsInstrVSel = true;
-        switch (Instr.getOpcode()) {
-        default:
-          IsInstrVSel = false;
-          CC = (ARMCC::CondCodes)Instr.getOperand(IO - 1).getImm();
-          break;
-        case ARM::VSELEQD:
-        case ARM::VSELEQS:
-          CC = ARMCC::EQ;
-          break;
-        case ARM::VSELGTD:
-        case ARM::VSELGTS:
-          CC = ARMCC::GT;
-          break;
-        case ARM::VSELGED:
-        case ARM::VSELGES:
-          CC = ARMCC::GE;
-          break;
-        case ARM::VSELVSS:
-        case ARM::VSELVSD:
-          CC = ARMCC::VS;
-          break;
-        }
 
-        if (Sub) {
-          ARMCC::CondCodes NewCC = getSwappedCondition(CC);
-          if (NewCC == ARMCC::AL)
-            return false;
-          // If we have SUB(r1, r2) and CMP(r2, r1), the condition code based
-          // on CMP needs to be updated to be based on SUB.
-          // Push the condition code operands to OperandsToUpdate.
-          // If it is safe to remove CmpInstr, the condition code of these
-          // operands will be modified.
-          if (SrcReg2 != 0 && Sub->getOperand(1).getReg() == SrcReg2 &&
-              Sub->getOperand(2).getReg() == SrcReg) {
-            // VSel doesn't support condition code update.
-            if (IsInstrVSel)
-              return false;
-            OperandsToUpdate.push_back(
-                std::make_pair(&((*I).getOperand(IO - 1)), NewCC));
-          }
-        } else {
-          // No Sub, so this is x = <op> y, z; cmp x, 0.
-          switch (CC) {
-          case ARMCC::EQ: // Z
-          case ARMCC::NE: // Z
-          case ARMCC::MI: // N
-          case ARMCC::PL: // N
-          case ARMCC::AL: // none
-            // CPSR can be used multiple times, we should continue.
-            break;
-          case ARMCC::HS: // C
-          case ARMCC::LO: // C
-          case ARMCC::VS: // V
-          case ARMCC::VC: // V
-          case ARMCC::HI: // C Z
-          case ARMCC::LS: // C Z
-          case ARMCC::GE: // N V
-          case ARMCC::LT: // N V
-          case ARMCC::GT: // Z N V
-          case ARMCC::LE: // Z N V
-            // The instruction uses the V bit or C bit which is not safe.
-            return false;
-          }
-        }
-      }
-    }
 
-    // If CPSR is not killed nor re-defined, we should check whether it is
-    // live-out. If it is live-out, do not optimize.
-    if (!isSafe) {
-      MachineBasicBlock *MBB = CmpInstr.getParent();
-      for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
-               SE = MBB->succ_end(); SI != SE; ++SI)
-        if ((*SI)->isLiveIn(ARM::CPSR))
-          return false;
-    }
 
-    // Toggle the optional operand to CPSR (if it exists - in Thumb1 we always
-    // set CPSR so this is represented as an explicit output)
-    if (!IsThumb1) {
-      MI->getOperand(5).setReg(ARM::CPSR);
-      MI->getOperand(5).setIsDef(true);
-    }
-    assert(!isPredicated(*MI) && "Can't use flags from predicated instruction");
-    CmpInstr.eraseFromParent();
 
-    // Modify the condition code of operands in OperandsToUpdate.
-    // Since we have SUB(r1, r2) and CMP(r2, r1), the condition code needs to
-    // be changed from r2 > r1 to r1 < r2, from r2 < r1 to r1 > r2, etc.
-    for (unsigned i = 0, e = OperandsToUpdate.size(); i < e; i++)
-      OperandsToUpdate[i].first->setImm(OperandsToUpdate[i].second);
-    return true;
-  }
-  }
-  
-  return false;
+  return true;
 }
 
 bool ARMBaseInstrInfo::FoldImmediate(MachineInstr &UseMI, MachineInstr &DefMI,
                                      unsigned Reg,
                                      MachineRegisterInfo *MRI) const {
   // Fold large immediates into add, sub, or, xor.
   unsigned DefOpc = DefMI.getOpcode();
   if (DefOpc != ARM::t2MOVi32imm && DefOpc != ARM::MOVi32imm)

test/CodeGen/ARM/mul-cmp-peephole.ll

+; RUN: llc < %s -mtriple=thumb-none-eabi | FileCheck %s
+
+; Check that we do the peephole optimisation.
+define i32 @f(i32 %a, i32 %b) {
+entry:
+; CHECK-LABEL: f:
+; CHECK: muls
+; CHECK-NOT: cmp
+  %mul = mul nsw i32 %b, %a
+  %cmp = icmp eq i32 %mul, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+; Check that we don't reorder the muls and move it to after the store
+define i32 @g(i32 %a, i32 %b) {
+entry:
+; CHECK-LABEL: g:
+; CHECK: muls
+; CHECK-NEXT: str
+  %retval = alloca i32, align 4
+  %a.addr = alloca i32, align 4
+  %b.addr = alloca i32, align 4
+  %mul = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  store i32 %b, i32* %b.addr, align 4
+  %0 = load i32, i32* %a.addr, align 4
+  %1 = load i32, i32* %b.addr, align 4
+  %mul1 = mul nsw i32 %0, %1
+  store i32 %mul1, i32* %mul, align 4
+  %2 = load i32, i32* %mul, align 4
+  %cmp = icmp eq i32 %2, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 42, i32* %retval, align 4
+  br label %return
+
+if.end:
+  store i32 1, i32* %retval, align 4
+  br label %return
+
+return:
+  %3 = load i32, i32* %retval, align 4
+  ret i32 %3
+}