[AArch64][CodeGen] Fix of incorrect peephole optimization in AArch64InstrInfo::optimizeCompareInstr + peephole rules for Cmp+Brc

[eastig]

Summary

AArch64 peephole optimizer tries to remove a compare instruction. One case is comparison with 0: CmpInst %vreg, 0. It removes CmpInst and modifies the instruction defining ‘%vreg’ to the S version. It is not checked that the S version and CmpInst produce the same condition flags.
For example the following code

%vreg7<def> = ANDWri %vreg6<kill>, 15; GPR32sp:%vreg7 GPR32:%vreg6
%vreg8<def> = SUBSWri %vreg7<kill>, 0, 0, %NZCV<imp-def>; GPR32:%vreg8 GPR32sp:%vreg7
Bcc 3, <BB#2>, %NZCV<imp-use>

is transformed to the incorrect code:

%vreg7<def> = ANDSWri %vreg6<kill>, 15, %NZCV<imp-def>; GPR32common:%vreg7 GPR32:%vreg6
Bcc 3, <BB#2>, %NZCV<imp-use>

It's incorrect because 'SUBSWri %vreg7<kill>, 0' always sets the carry flag to 1 but 'ANDSWri %vreg6<kill>, 15' always sets the carry flag to 0. As a result Bcc which checks the carry flag is not working as expected.

The submitted patch contains the fix of the defect and additional peephole rules for Cmp+Brc sequences. New regression tests are created.

Changes description:

• Refactoring:

a. Function name ‘modifiesConditionCode’ is changed to ‘areCFlagsAccessedBetweenInstrs’ to reflect that the function can check modifying accesses, reading accesses or both.
b. Function ‘AArch64InstrInfo::optimizeCompareInstr’

• Documented the function
• Cmp_NZCV is DeadNZCVIdx to reflect that it is an operand index of dead NZCV
• The code for the case of substituting CmpInstr is put into separate functions the main of them is ‘substituteCmpInstr’.

• Fix of the defect:

A new algorithm was implemented:

1. It’s checked that the same condition code is read by instructions after CmpInstr and before the next modification of NZCV. The optimization is not applied if different condition codes are used. It might be difficult to find a candidate for substitution to satisfy all of them. I think this case with multiple used condition codes does not happen often.
2. Then it’s checked that the instruction which defines a register for CmpInstr can produce the needed condition code itself or its S variant. If it or its S variant can produce then CmpInstr is removed.

• New peephole rules for Cmp+Brc:

The following rules were implemented:

SUBS reg, 0; B.LO => B <false path>
SUBS reg, 0; B.HS <label> => B <label>

• Testing status: all existing + new tests passed.

[eastig]

Used arc to have the context of changes.

[eastig]

Ping.

[jmolloy]

Hi Evgeny,

Thanks for doing this. The documentation and cleanup is especially welcome.

I have comments below, but the main comment is that this needs to be split into two separate patches. One that performs a NFC refactoring, and another that actually fixes your bug. As is, it's very difficult for me to validate that the functional changes you've introduced are all required and what exactly they do differently.

Cheers,

James

lib/Target/AArch64/AArch64InstrInfo.cpp

825

Can you not just use

std::find(MachineBasicBlock::reverse_iterator(To), To->getParent()->rend(), *From) ?

834

I think inlining the isAccess call in here would make things easier to read:

if ( (AccessToCheck & AK_Write) && ...)

854

This could be better written as :

auto BeginInstrI = std::next(Instr->getIterator());

871

Braces go on the same line as the case.

887

Braces go on the same line as the case.

912

The formatting of this is too verbose. The original code had one LoC per case, you have three. Please reformat as the original.

960

Not properly indented here

969

Unneeded line break here

1013

Brace should be on the same line as the case.

[eastig]

In D18318#386639, @jmolloy wrote:

I have comments below, but the main comment is that this needs to be split into two separate patches. One that performs a NFC refactoring, and another that actually fixes your bug.

Thank you for reviewing and advice. I will split it into three patches:

1. Refactoring
2. Bug fix
3. New peephole rules for cmp+brc

[eastig]

lib/Target/AArch64/AArch64InstrInfo.cpp

825

No, we cannot. '==' is not defined for MachineInstr. We can check either iterators or pointers.

lib/Target/AArch64/AArch64InstrInfo.h

public:
   getSerializableDirectMachineOperandTargetFlags() const override;
   ArrayRef<std::pair<unsigned, const char *>>
   getSerializableBitmaskMachineOperandTargetFlags() const override;
 
 private:
   void instantiateCondBranch(MachineBasicBlock &MBB, DebugLoc DL,
                              MachineBasicBlock *TBB,
                              ArrayRef<MachineOperand> Cond) const;
+  bool substituteCmpInstr(MachineInstr *CmpInstr,
+                          unsigned SrcReg,
+                          AArch64CC::CondCode NeededCondCode,
+                          const MachineRegisterInfo *MRI) const;
+  bool optimizeCmpAndBrcSeq(MachineInstr *BrcInstr) const;
 };
 
 /// emitFrameOffset - Emit instructions as needed to set DestReg to SrcReg
 /// plus Offset.  This is intended to be used from within the prolog/epilog
 /// insertion (PEI) pass, where a virtual scratch register may be allocated
 /// if necessary, to be replaced by the scavenger at the end of PEI.
 void emitFrameOffset(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                      DebugLoc DL, unsigned DestReg, unsigned SrcReg, int Offset,

lib/Target/AArch64/AArch64InstrInfo.cpp

 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TargetRegistry.h"
+#include <algorithm>
 
 using namespace llvm;
 
 #define GET_INSTRINFO_CTOR_DTOR
 #include "AArch64GenInstrInfo.inc"
 
 AArch64InstrInfo::AArch64InstrInfo(const AArch64Subtarget &STI)
     : AArch64GenInstrInfo(AArch64::ADJCALLSTACKDOWN, AArch64::ADJCALLSTACKUP),
case AArch64::SUBSXri:
     return MIDefinesZeroReg ? AArch64::SUBSXri : AArch64::SUBXri;
   case AArch64::SUBSXrs:
     return MIDefinesZeroReg ? AArch64::SUBSXrs : AArch64::SUBXrs;
   case AArch64::SUBSXrx:
     return AArch64::SUBXrx;
   }
 }
 
-/// True when condition code could be modified on the instruction
-/// trace starting at from and ending at to.
-static bool modifiesConditionCode(MachineInstr *From, MachineInstr *To,
-                                  const bool CheckOnlyCCWrites,
-                                  const TargetRegisterInfo *TRI) {
+enum AccessKind {
+  AK_Write = 0x01,
+  AK_Read  = 0x10,
+  AK_All   = 0x11
+};
+
+inline bool isAccess(AccessKind Access1, AccessKind Access2) {
+  return Access1 & Access2;
+}
+
+/// True when condition flags are accessed (either by writing or reading)
+/// on the instruction trace starting at From and ending at To.
+///
+/// Note: If From and To are from different blocks it's assumed CC are accessed
+///       on the path.
+static bool areCFlagsAccessedBetweenInstrs(MachineInstr *From, MachineInstr *To,
+                                const TargetRegisterInfo *TRI,
+                                const AccessKind AccessToCheck = AK_All) {
   // We iterate backward starting \p To until we hit \p From
   MachineBasicBlock::iterator I = To, E = From, B = To->getParent()->begin();
 
   // Early exit if To is at the beginning of the BB.
   if (I == B)
     return true;
 
-  // Check whether the definition of SrcReg is in the same basic block as
-  // Compare. If not, assume the condition code gets modified on some path.
+  // Check whether the instructions are in the same basic block
+  // If not, assume the condition flags might get modified somewhere.
   if (To->getParent() != From->getParent())
     return true;
 
-  // Check that NZCV isn't set on the trace.
+  // From must be above To.
+  assert(std::find_if(MachineBasicBlock::reverse_iterator(To),
+                   To->getParent()->rend(),
+                   [From](MachineInstr &MI) {
+                     return &MI == From;
+                   }) != To->getParent()->rend());
+
   for (--I; I != E; --I) {
     const MachineInstr &Instr = *I;
 
-    if (Instr.modifiesRegister(AArch64::NZCV, TRI) ||
-        (!CheckOnlyCCWrites && Instr.readsRegister(AArch64::NZCV, TRI)))
-      // This instruction modifies or uses NZCV after the one we want to
-      // change.
+    if ((isAccess(AccessToCheck, AK_Write) && Instr.modifiesRegister(AArch64::NZCV, TRI)) ||
+        (isAccess(AccessToCheck, AK_Read)  && Instr.readsRegister(AArch64::NZCV, TRI)))
       return true;
-    if (I == B)
-      // We currently don't allow the instruction trace to cross basic
-      // block boundaries
+  }
+  return false;
+}
+
+/// Check if AArch64::NZCV should be alive in successors of MBB.
+static bool areCFlagsAliveInSuccessors(MachineBasicBlock *MBB) {
+  for (auto *BB : MBB->successors())
+    if (BB->isLiveIn(AArch64::NZCV))
       return true;
+  return false;
+}
+
+/// Find the first modification of AArch64::NZCV after the specified instruction.
+static MachineBasicBlock::iterator
+firstModificationOfCondFlagsAfterInstr(MachineInstr *Instr,
+        const TargetRegisterInfo *TRI) {
+  assert(Instr);
+  MachineBasicBlock::iterator BeginInstrI = Instr;
+  ++BeginInstrI;
+  return std::find_if(BeginInstrI, Instr->getParent()->end(),
+          [TRI](MachineInstr &MI) {
+            return MI.modifiesRegister(AArch64::NZCV, TRI);
+          });
+}
+
+/// Find a condition code used by the instruction.
+/// Returns AArch64CC::Invalid if either the instruction does not use condition
+/// codes or we don't optimize CmpInstr in the presence of such instructions.
+static AArch64CC::CondCode findCondCodeUsedByInstr(MachineInstr &Instr) {
+  switch (Instr.getOpcode()) {
+    default:
+      return AArch64CC::Invalid;
+
+    case AArch64::Bcc:
+    {
+      int Idx = Instr.findRegisterUseOperandIdx(AArch64::NZCV);
+      assert(Idx >= 2);
+      return static_cast<AArch64CC::CondCode>(Instr.getOperand(Idx - 2).getImm());
+    }
+
+    case AArch64::CSINVWr:
+    case AArch64::CSINVXr:
+    case AArch64::CSINCWr:
+    case AArch64::CSINCXr:
+    case AArch64::CSELWr:
+    case AArch64::CSELXr:
+    case AArch64::CSNEGWr:
+    case AArch64::CSNEGXr:
+    case AArch64::FCSELSrrr:
+    case AArch64::FCSELDrrr:
+    {
+      int Idx = Instr.findRegisterUseOperandIdx(AArch64::NZCV);
+      assert(Idx >= 1);
+      return static_cast<AArch64CC::CondCode>(Instr.getOperand(Idx - 1).getImm());
+    }
+  }
+}
+
+/// Get opcode of S version of Instr.
+/// If Instr is S version its opcode is returned.
+/// AArch64::INSTRUCTION_LIST_END is returned if Instr does not have S version
+/// or we are not interested in it.
+static unsigned sForm(MachineInstr &Instr) {
+  switch (Instr.getOpcode()) {
+    default:
+      return AArch64::INSTRUCTION_LIST_END;
+
+    case AArch64::ADDSWrr:
+    case AArch64::ADDSWri:
+    case AArch64::ADDSXrr:
+    case AArch64::ADDSXri:
+    case AArch64::SUBSWrr:
+    case AArch64::SUBSWri:
+    case AArch64::SUBSXrr:
+    case AArch64::SUBSXri:
+      return Instr.getOpcode();
+
+    case AArch64::ADDWrr:
+      return AArch64::ADDSWrr;
+
+    case AArch64::ADDWri:
+      return AArch64::ADDSWri;
+
+    case AArch64::ADDXrr:
+      return AArch64::ADDSXrr;
+
+    case AArch64::ADDXri:
+      return AArch64::ADDSXri;
+
+    case AArch64::ADCWr:
+      return AArch64::ADCSWr;
+
+    case AArch64::ADCXr:
+      return AArch64::ADCSXr;
+
+    case AArch64::SUBWrr:
+      return AArch64::SUBSWrr;
+
+    case AArch64::SUBWri:
+      return AArch64::SUBSWri;
+
+    case AArch64::SUBXrr:
+      return AArch64::SUBSXrr;
+
+    case AArch64::SUBXri:
+      return AArch64::SUBSXri;
+
+    case AArch64::SBCWr:
+      return AArch64::SBCSWr;
+
+    case AArch64::SBCXr:
+      return AArch64::SBCSXr;
+
+    case AArch64::ANDWri:
+      return AArch64::ANDSWri;
+
+    case AArch64::ANDXri:
+      return AArch64::ANDSXri;
+  }
+}
+
+/// Check if Instr can produce a needed condition code.
+static bool canInstrProduceCondCode(MachineInstr &Instr,
+        AArch64CC::CondCode NeededCondCode) {
+  switch (NeededCondCode) {
+    default:
+      return false;
+
+    case AArch64CC::NE:
+      switch (Instr.getOpcode()) {
+        default:
+          break;
+
+        case AArch64::ADDWri:
+        case AArch64::ADDXri:
+        case AArch64::ADDSWri:
+        case AArch64::ADDSXri:
+          return Instr.getOperand(1).isFI()
+                  && !Instr.getOperand(2).getImm();
+      }
+      break;
   }
   return false;
 }
-/// optimizeCompareInstr - Convert the instruction supplying the argument to the
-/// comparison into one that sets the zero bit in the flags register.
+
+static bool isADDS(unsigned Opcode) {
+  return AArch64::ADDSWri <= Opcode && Opcode <= AArch64::ADDSXrx64;
+}
+
+static bool isSUBS(unsigned Opcode) {
+  return AArch64::SUBSWri <= Opcode && Opcode <= AArch64::SUBSXrx64;
+}
+
+/// Substitute CmpInstr with another instruction which produces a needed
+/// condition code.
+/// Return true on success.
+bool AArch64InstrInfo::substituteCmpInstr(MachineInstr *CmpInstr,
+        unsigned SrcReg,
+        AArch64CC::CondCode NeededCondCode,
+        const MachineRegisterInfo *MRI) const {
+  assert(CmpInstr);
+  assert(MRI);
+
+  const TargetRegisterInfo *TRI = &getRegisterInfo();
+  MachineInstr *MI = MRI->getUniqueVRegDef(SrcReg);
+  if (!MI)
+    return false;
+
+  switch (NeededCondCode) {
+    default:
+      return false;
+
+    case AArch64CC::EQ:
+    case AArch64CC::NE:
+    case AArch64CC::MI:
+    case AArch64CC::PL:
+    {
+      unsigned MiSOpcode = sForm(*MI);
+      if ((isADDS(CmpInstr->getOpcode()) && isADDS(MiSOpcode))
+              || (isSUBS(CmpInstr->getOpcode()) && isSUBS(MiSOpcode))
+              || canInstrProduceCondCode(*MI, NeededCondCode)) {
+        MI->setDesc(get(MiSOpcode));
+        CmpInstr->eraseFromParent();
+        bool succeeded = UpdateOperandRegClass(MI);
+        (void)succeeded;
+        assert(succeeded && "Some operands reg class are incompatible!");
+        MI->addRegisterDefined(AArch64::NZCV, TRI);
+        return true;
+      }
+    }
+  }
+
+  return false;
+}
+
+/// Try to optimize a compare instruction. A compare instruction is an
+/// instruction which produces AArch64::NZCV. It can be truly compare instruction
+/// when there are no uses of its destination register.
+///
+/// The following steps are tried in order:
+/// 1. Convert CmpInstr into an unconditional version.
+/// 2. Remove CmpInstr if above there is an instruction producing a needed
+///    condition code or an instruction which can be converted into such an instruction.
+///    Only comparison with zero is supported.
 bool AArch64InstrInfo::optimizeCompareInstr(
     MachineInstr *CmpInstr, unsigned SrcReg, unsigned SrcReg2, int CmpMask,
     int CmpValue, const MachineRegisterInfo *MRI) const {
+  assert(CmpInstr);
+  assert(CmpInstr->getParent());
+  assert(MRI);
 
   // Replace SUBSWrr with SUBWrr if NZCV is not used.
-  int Cmp_NZCV = CmpInstr->findRegisterDefOperandIdx(AArch64::NZCV, true);
-  if (Cmp_NZCV != -1) {
+  int DeadNZCVIdx = CmpInstr->findRegisterDefOperandIdx(AArch64::NZCV, true);
+  if (DeadNZCVIdx != -1) {
     if (CmpInstr->definesRegister(AArch64::WZR) ||
         CmpInstr->definesRegister(AArch64::XZR)) {
       CmpInstr->eraseFromParent();
       return true;
     }
     unsigned Opc = CmpInstr->getOpcode();
     unsigned NewOpc = convertFlagSettingOpcode(CmpInstr);
     if (NewOpc == Opc)
       return false;
     const MCInstrDesc &MCID = get(NewOpc);
     CmpInstr->setDesc(MCID);
-    CmpInstr->RemoveOperand(Cmp_NZCV);
+    CmpInstr->RemoveOperand(DeadNZCVIdx);
     bool succeeded = UpdateOperandRegClass(CmpInstr);
     (void)succeeded;
     assert(succeeded && "Some operands reg class are incompatible!");
     return true;
   }
 
   // Continue only if we have a "ri" where immediate is zero.
   // FIXME:CmpValue has already been converted to 0 or 1 in analyzeCompare
   // function.
   assert((CmpValue == 0 || CmpValue == 1) && "CmpValue must be 0 or 1!");
   if (CmpValue != 0 || SrcReg2 != 0)
     return false;
 
   // CmpInstr is a Compare instruction if destination register is not used.
   if (!MRI->use_nodbg_empty(CmpInstr->getOperand(0).getReg()))
     return false;
 
-  // Get the unique definition of SrcReg.
-  MachineInstr *MI = MRI->getUniqueVRegDef(SrcReg);
-  if (!MI)
-    return false;
-
-  bool CheckOnlyCCWrites = false;
   const TargetRegisterInfo *TRI = &getRegisterInfo();
-  if (modifiesConditionCode(MI, CmpInstr, CheckOnlyCCWrites, TRI))
-    return false;
 
-  unsigned NewOpc = MI->getOpcode();
-  switch (MI->getOpcode()) {
-  default:
-    return false;
-  case AArch64::ADDSWrr:
-  case AArch64::ADDSWri:
-  case AArch64::ADDSXrr:
-  case AArch64::ADDSXri:
-  case AArch64::SUBSWrr:
-  case AArch64::SUBSWri:
-  case AArch64::SUBSXrr:
-  case AArch64::SUBSXri:
-    break;
-  case AArch64::ADDWrr:    NewOpc = AArch64::ADDSWrr; break;
-  case AArch64::ADDWri:    NewOpc = AArch64::ADDSWri; break;
-  case AArch64::ADDXrr:    NewOpc = AArch64::ADDSXrr; break;
-  case AArch64::ADDXri:    NewOpc = AArch64::ADDSXri; break;
-  case AArch64::ADCWr:     NewOpc = AArch64::ADCSWr; break;
-  case AArch64::ADCXr:     NewOpc = AArch64::ADCSXr; break;
-  case AArch64::SUBWrr:    NewOpc = AArch64::SUBSWrr; break;
-  case AArch64::SUBWri:    NewOpc = AArch64::SUBSWri; break;
-  case AArch64::SUBXrr:    NewOpc = AArch64::SUBSXrr; break;
-  case AArch64::SUBXri:    NewOpc = AArch64::SUBSXri; break;
-  case AArch64::SBCWr:     NewOpc = AArch64::SBCSWr; break;
-  case AArch64::SBCXr:     NewOpc = AArch64::SBCSXr; break;
-  case AArch64::ANDWri:    NewOpc = AArch64::ANDSWri; break;
-  case AArch64::ANDXri:    NewOpc = AArch64::ANDSXri; break;
-  }
-
-  // Scan forward for the use of NZCV.
-  // When checking against MI: if it's a conditional code requires
-  // checking of V bit, then this is not safe to do.
-  // It is safe to remove CmpInstr if NZCV is redefined or killed.
-  // If we are done with the basic block, we need to check whether NZCV is
-  // live-out.
-  bool IsSafe = false;
-  for (MachineBasicBlock::iterator I = CmpInstr,
-                                   E = CmpInstr->getParent()->end();
-       !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(AArch64::NZCV)) {
-        IsSafe = true;
-        break;
-      }
-      if (!MO.isReg() || MO.getReg() != AArch64::NZCV)
-        continue;
-      if (MO.isDef()) {
-        IsSafe = true;
-        break;
-      }
+  AArch64CC::CondCode NeededCondCode = AArch64CC::Invalid;
+  MachineBasicBlock::iterator CFlagsFirstModificationLoc
+          = firstModificationOfCondFlagsAfterInstr(CmpInstr, TRI);
+  for (MachineBasicBlock::iterator I = CmpInstr;
+          ++I != CFlagsFirstModificationLoc;) {
+    MachineInstr &MI = *I;
+    if (!MI.readsRegister(AArch64::NZCV, TRI))
 
-      // Decode the condition code.
-      unsigned Opc = Instr.getOpcode();
-      AArch64CC::CondCode CC;
-      switch (Opc) {
-      default:
-        return false;
-      case AArch64::Bcc:
-        CC = (AArch64CC::CondCode)Instr.getOperand(IO - 2).getImm();
-        break;
-      case AArch64::CSINVWr:
-      case AArch64::CSINVXr:
-      case AArch64::CSINCWr:
-      case AArch64::CSINCXr:
-      case AArch64::CSELWr:
-      case AArch64::CSELXr:
-      case AArch64::CSNEGWr:
-      case AArch64::CSNEGXr:
-      case AArch64::FCSELSrrr:
-      case AArch64::FCSELDrrr:
-        CC = (AArch64CC::CondCode)Instr.getOperand(IO - 1).getImm();
-        break;
-      }
+    AArch64CC::CondCode CC = findCondCodeUsedByInstr(MI);
+    if (CC == AArch64CC::Invalid)
 
-      // It is not safe to remove Compare instruction if Overflow(V) is used.
-      switch (CC) {
-      default:
-        // NZCV can be used multiple times, we should continue.
-        break;
-      case AArch64CC::VS:
-      case AArch64CC::VC:
-      case AArch64CC::GE:
-      case AArch64CC::LT:
-      case AArch64CC::GT:
-      case AArch64CC::LE:
-        return false;
-      }
-    }
-  }
+    if (NeededCondCode == AArch64CC::Invalid)
+      NeededCondCode = CC;
+    else if (CC != NeededCondCode) {
+      // Different condition codes are used it might not be safe to remove CmpInstr.
 
-  // If NZCV 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 *ParentBlock = CmpInstr->getParent();
-    for (auto *MBB : ParentBlock->successors())
-      if (MBB->isLiveIn(AArch64::NZCV))
-        return false;
+  // There are instructions which read and write flags at the same time.
+  if (NeededCondCode == AArch64CC::Invalid
+          && CFlagsFirstModificationLoc != CmpInstr->getParent()->end()) {
+    NeededCondCode = findCondCodeUsedByInstr(*CFlagsFirstModificationLoc);
+    if (NeededCondCode == AArch64CC::Invalid)
   }
 
-  // Update the instruction to set NZCV.
-  MI->setDesc(get(NewOpc));
-  CmpInstr->eraseFromParent();
-  bool succeeded = UpdateOperandRegClass(MI);
-  (void)succeeded;
-  assert(succeeded && "Some operands reg class are incompatible!");
-  MI->addRegisterDefined(AArch64::NZCV, TRI);
-  return true;
+  // Uses are not in the parent of CmpInstr.
+  if (NeededCondCode == AArch64CC::Invalid
+          || areCFlagsAliveInSuccessors(CmpInstr->getParent()))
+    return false;
+
+  return substituteCmpInstr(CmpInstr, SrcReg, NeededCondCode, MRI);
 }
 
 bool
 AArch64InstrInfo::expandPostRAPseudo(MachineBasicBlock::iterator MI) const {
   if (MI->getOpcode() != TargetOpcode::LOAD_STACK_GUARD)
     return false;
 
   MachineBasicBlock &MBB = *MI->getParent();
void AArch64InstrInfo::genAlternativeCodeSequence(
   } // end switch (Pattern)
   // Record MUL and ADD/SUB for deletion
   DelInstrs.push_back(MUL);
   DelInstrs.push_back(&Root);
 
   return;
 }
 
+static bool isCmpWithZero(MachineInstr *CmpInstr) {
+  assert(CmpInstr);
+  return (CmpInstr->getOpcode() == AArch64::SUBSWri
+          || CmpInstr->getOpcode() == AArch64::SUBSXri)
+          && !CmpInstr->getOperand(2).getImm();
+}
+
+/// Optimize Cmp and Brc sequences.
+/// When we compare with zero a result is known. We can figure out
+/// which path is taken by Brc. We substitute Brc by an unconditional
+/// branch to that path.
+///
+/// Rules:
+///  SUBS reg, 0; B.LO         => B <false path>
+///  SUBS reg, 0; B.HS <label> => B <label>
+bool AArch64InstrInfo::optimizeCmpAndBrcSeq(MachineInstr *BrcInstr) const {
+  assert(BrcInstr);
+
+  const TargetRegisterInfo *TRI = &getRegisterInfo();
+  auto CmpInstrLoc = std::find_if(MachineBasicBlock::reverse_iterator(BrcInstr),
+          BrcInstr->getParent()->rend(),
+          [TRI](MachineInstr &MI) {
+            return MI.modifiesRegister(AArch64::NZCV, TRI);
+          });
+
+  if (CmpInstrLoc == BrcInstr->getParent()->rend())
+    return false;
+
+  MachineInstr *CmpInstr = &*CmpInstrLoc;
+  assert(CmpInstr);
+  if (!isCmpWithZero(CmpInstr)
+      || areCFlagsAccessedBetweenInstrs(CmpInstr, BrcInstr, TRI)
+      || areCFlagsAliveInSuccessors(BrcInstr->getParent()))
+    return false;
+
+  AArch64CC::CondCode CC = static_cast<AArch64CC::CondCode>(BrcInstr->getOperand(0).getImm());
+  bool RemoveCmp   = false;
+  bool UseTruePath = false;
+  switch (CC) {
+    case AArch64CC::HS:
+      UseTruePath = true;
+    case AArch64CC::LO:
+      RemoveCmp = true;
+      break;
+
+    default:
+      return false;
+  }
+
+  assert(RemoveCmp);
+
+  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+  SmallVector<MachineOperand, 4> Cond;
+  assert(CmpInstr->getParent());
+  if (AnalyzeBranch(*CmpInstr->getParent(), TBB, FBB, Cond))
+    return false;
+
+  assert(TBB != FBB);
+  assert((TBB && !FBB) || (TBB && FBB));
+  if (!FBB) {
+    // Find fallthrough basic block
+    auto BBI = std::find_if(CmpInstr->getParent()->succ_begin(),
+                 CmpInstr->getParent()->succ_end(),
+               [TBB](MachineBasicBlock *BB) {
+                 assert(BB);
+                 return !BB->isEHPad() && BB != TBB;
+               });
+    assert(BBI != CmpInstr->getParent()->succ_end());
+    FBB = *BBI;
+  }
+  MachineBasicBlock *NewBrTarget = nullptr;
+  if (UseTruePath) {
+    NewBrTarget = TBB;
+    BrcInstr->getParent()->removeSuccessor(FBB);
+  } else {
+    NewBrTarget = FBB;
+    BrcInstr->getParent()->removeSuccessor(TBB);
+  }
+  assert(NewBrTarget);
+  while (BrcInstr->getNumOperands())
+    BrcInstr->RemoveOperand(BrcInstr->getNumOperands() - 1);
+  BrcInstr->setDesc(get(AArch64::B));
+  BrcInstr->addOperand(MachineOperand::CreateMBB(NewBrTarget));
+
+  CmpInstr->eraseFromParent();
+
+  return true;
+}
+
 /// \brief Replace csincr-branch sequence by simple conditional branch
 ///
 /// Examples:
 /// 1.
 ///   csinc  w9, wzr, wzr, <condition code>
 ///   tbnz   w9, #0, 0x44
 /// to
 ///   b.<inverted condition code>

 bool AArch64InstrInfo::optimizeCondBranch(MachineInstr *MI) const {
   bool IsNegativeBranch = false;
   bool IsTestAndBranch = false;
   unsigned TargetBBInMI = 0;
   switch (MI->getOpcode()) {
   default:
     llvm_unreachable("Unknown branch instruction?");
   case AArch64::Bcc:
-    return false;
+    return optimizeCmpAndBrcSeq(MI);
   case AArch64::CBZW:
   case AArch64::CBZX:
     TargetBBInMI = 1;
     break;
   case AArch64::CBNZW:
   case AArch64::CBNZX:
     TargetBBInMI = 1;
     IsNegativeBranch = true;
if (!(DefMI->getOperand(1).getReg() == AArch64::WZR &&
         !(DefMI->getOperand(1).getReg() == AArch64::XZR &&
           DefMI->getOperand(2).getReg() == AArch64::XZR))
       return false;
 
     if (DefMI->findRegisterDefOperandIdx(AArch64::NZCV, true) != -1)
       return false;
 
     AArch64CC::CondCode CC = (AArch64CC::CondCode)DefMI->getOperand(3).getImm();
-    bool CheckOnlyCCWrites = true;
     // Convert only when the condition code is not modified between
     // the CSINC and the branch. The CC may be used by other
     // instructions in between.
-    if (modifiesConditionCode(DefMI, MI, CheckOnlyCCWrites, &getRegisterInfo()))
+    if (areCFlagsAccessedBetweenInstrs(DefMI, MI, &getRegisterInfo(), AK_Write))
       return false;
     MachineBasicBlock &RefToMBB = *MBB;
     MachineBasicBlock *TBB = MI->getOperand(TargetBBInMI).getMBB();
     DebugLoc DL = MI->getDebugLoc();
     if (IsNegativeBranch)
       CC = AArch64CC::getInvertedCondCode(CC);
     BuildMI(RefToMBB, MI, DL, get(AArch64::Bcc)).addImm(CC).addMBB(TBB);
     MI->eraseFromParent();

test/CodeGen/AArch64/cmp-bcc-opt.ll

+; RUN: llc -mtriple=aarch64-linux-gnu -O3 -o - %s | FileCheck --check-prefix SUBS-B_LO %s
+; RUN: llc -mtriple=aarch64-linux-gnu -O3 -o - %s | FileCheck --check-prefix SUBS64-B_LO %s
+; RUN: llc -mtriple=aarch64-linux-gnu -O3 -o - %s | FileCheck --check-prefix SUBS-B_HS %s
+; RUN: llc -mtriple=aarch64-linux-gnu -O3 -o - %s | FileCheck --check-prefix SUBS64-B_HS %s
+
+; This file contains tests for the AArch64 cmp/bcc optimizer
+
+declare i32 @one(...)
+
+@a = external global i8, align 1
+@b = external global i8, align 1
+
+; Test that
+;  %vreg8<def> = SUBSWri %vreg7<kill>, 0, 0, %NZCV<imp-def>;
+;  Bcc 3, <BB#2>, %NZCV<imp-use>
+; is replaced with an unconditional branch
+define i32 @test01() nounwind {
+; SUBS-B_LO:test01: // @test01
+; SUBS-B_LO-NEXT:// BB#0: // %entry
+; SUBS-B_LO-NEXT: b one
+; SUBS-B_LO-NEXT:.Lfunc_end0:
+entry:
+  %0 = load i8, i8* @a, align 1
+  %conv = zext i8 %0 to i32
+  %1 = load i8, i8* @b, align 1
+  %conv1 = zext i8 %1 to i32
+  %shl = shl i32 %conv, %conv1
+  %conv3 = and i32 %shl, 65535
+  %cmp = icmp ult i32 %conv3, 0
+  br i1 %cmp, label %cleanup, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 bitcast (i32 (...)* @one to i32 ()*)() #2
+  br label %cleanup
+
+cleanup:                                          ; preds = %entry, %if.then
+  %retval.0 = phi i32 [ %call, %if.then ], [ 0, %entry ]
+  ret i32 %retval.0
+}
+
+; Test that
+;  %vreg8<def> = SUBSXri %vreg7<kill>, 0, 0, %NZCV<imp-def>;
+;  Bcc 3, <BB#2>, %NZCV<imp-use>
+; is replaced with an unconditional branch
+define i32 @test02() nounwind {
+; SUBS64-B_LO:test02: // @test02
+; SUBS64-B_LO-NEXT:// BB#0: // %entry
+; SUBS64-B_LO-NEXT: b one
+; SUBS64-B_LO-NEXT:.Lfunc_end1:
+entry:
+  %0 = load i8, i8* @a, align 1
+  %conv = zext i8 %0 to i64
+  %1 = load i8, i8* @b, align 1
+  %conv1 = zext i8 %1 to i64
+  %shl = shl i64 %conv, %conv1
+  %conv3 = and i64 %shl, 65535
+  %cmp = icmp ult i64 %conv3, 0
+  br i1 %cmp, label %cleanup, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 bitcast (i32 (...)* @one to i32 ()*)() #2
+  br label %cleanup
+
+cleanup:                                          ; preds = %entry, %if.then
+  %retval.0 = phi i32 [ %call, %if.then ], [ 0, %entry ]
+  ret i32 %retval.0
+}
+
+; Test that
+;  %vreg8<def> = SUBSWri %vreg7<kill>, 0, 0, %NZCV<imp-def>;
+;  Bcc 2, <BB#2>, %NZCV<imp-use>
+; is replaced with an unconditional branch
+define i32 @test03() nounwind {
+; SUBS-B_HS:test03: // @test03
+; SUBS-B_HS-NEXT:// BB#0: // %entry
+; SUBS-B_HS-NEXT: mov w0, wzr
+; SUBS-B_HS-NEXT: ret
+; SUBS-B_HS-NEXT:.Lfunc_end2:
+entry:
+  %0 = load i8, i8* @a, align 1
+  %conv = zext i8 %0 to i32
+  %1 = load i8, i8* @b, align 1
+  %conv1 = zext i8 %1 to i32
+  %shl = shl i32 %conv, %conv1
+  %conv3 = and i32 %shl, 65535
+  %cmp = icmp uge i32 %conv3, 0
+  br i1 %cmp, label %cleanup, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 bitcast (i32 (...)* @one to i32 ()*)() #2
+  br label %cleanup
+
+cleanup:                                          ; preds = %entry, %if.then
+  %retval.0 = phi i32 [ %call, %if.then ], [ 0, %entry ]
+  ret i32 %retval.0
+}
+
+; Test that
+;  %vreg8<def> = SUBSXri %vreg7<kill>, 0, 0, %NZCV<imp-def>;
+;  Bcc 2, <BB#2>, %NZCV<imp-use>
+; is replaced with an unconditional branch
+define i32 @test04() nounwind {
+; SUBS64-B_HS:test04: // @test04
+; SUBS64-B_HS-NEXT:// BB#0: // %entry
+; SUBS64-B_HS-NEXT: mov w0, wzr
+; SUBS64-B_HS-NEXT: ret
+; SUBS64-B_HS-NEXT:.Lfunc_end3:
+entry:
+  %0 = load i8, i8* @a, align 1
+  %conv = zext i8 %0 to i64
+  %1 = load i8, i8* @b, align 1
+  %conv1 = zext i8 %1 to i64
+  %shl = shl i64 %conv, %conv1
+  %conv3 = and i64 %shl, 65535
+  %cmp = icmp uge i64 %conv3, 0
+  br i1 %cmp, label %cleanup, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i32 bitcast (i32 (...)* @one to i32 ()*)() #2
+  br label %cleanup
+
+cleanup:                                          ; preds = %entry, %if.then
+  %retval.0 = phi i32 [ %call, %if.then ], [ 0, %entry ]
+  ret i32 %retval.0
+}

test/CodeGen/AArch64/subs-to-sub-opt.ll

+; RUN: llc -mtriple=aarch64-linux-gnu -O3 -o - %s | FileCheck %s
+
+@a = external global i8, align 1
+@b = external global i8, align 1
+
+; Test that SUBS is replaced by SUB if condition flags are not used.
+define i32 @test01() nounwind {
+; CHECK: ldrb {{.*}}
+; CHECK-NEXT: ldrb {{.*}}
+; CHECK-NEXT: sub {{.*}}
+; CHECK-NEXT: cmn {{.*}}
+entry:
+  %0 = load i8, i8* @a, align 1
+  %conv = zext i8 %0 to i32
+  %1 = load i8, i8* @b, align 1
+  %conv1 = zext i8 %1 to i32
+  %s = sub nsw i32 %conv1, %conv
+  %cmp0 = icmp eq i32 %s, -1
+  %cmp1 = sext i1 %cmp0 to i8
+  store i8 %cmp1, i8* @a
+  ret i32 0
+}
+