Fix PR25526 by adding back limited cmpxchg pseudo-Insts

[t.p.northover]

Summary

Hi,

This is an attempt to fix the failure of cmpxchg at -O0 on AArch64. The issue is that fast-regalloc puts spills into ldxr/stxr loops, which can continually clear the exclusive monitor and block progress.

I really don't like having to re-add the pseudo-instructions, since they're error-prone and ugly, but I think I've tried everything else (in approximate order of preference):

• Emit libcalls: they don't exist in libgcc, so even if we could herd all other cats we'd break compatibility with existing versions of GCC.
• Handle the expanded @llvm.aarch64.ldxr/stxr intrinsics to do away with any vregs (so fast-regalloc can't botch them), either in DAG or FastISel. I tried both, but the IR comparison always creates more. No change.
• Change to a different register allocator at -O0. Too costly for compile-time performance and debug.
• A usesCustomInserter Pseudo-inst. Not really any better, but doesn't work anyway because we still have the vregs immediately after DAG.

About the one silver lining is that we only need to handle a very small subset of possible atomic operations, and not even many cmpxchg operations (I think we can treat them all as seq_cst, strong exchanges without violating correctness).

If anyone has any other ideas, please speak up. I'm quite happy to give implementing them a try if there's any hope of avoiding this hack.

Otherwise, OK to commit?

Cheers.

Tim.

[mcrosier]

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

2355

return nullptr;

[t.p.northover]

Comment at: lib/Target/AArch64/AArch64ISelDAGToDAG.cpp:2360
@@ -2325,1 +2359,3 @@
+ SelectCMP_SWAP(Node);
+ return 0;

case ISD::READ_REGISTER:

---

return nullptr;

Thanks Chad. Will do, sorry about that. I also realised I'd not
updated the comments properly yet. The one in AArch64InstrAtomics.td
is misleading and more elsewhere would probably help.

Tim.

[mcrosier]

In D16239#328201, @t.p.northover wrote:

Comment at: lib/Target/AArch64/AArch64ISelDAGToDAG.cpp:2360
@@ -2325,1 +2359,3 @@
+ SelectCMP_SWAP(Node);
+ return 0;

case ISD::READ_REGISTER:

---

return nullptr;

Thanks Chad. Will do, sorry about that. I also realised I'd not
updated the comments properly yet. The one in AArch64InstrAtomics.td
is misleading and more elsewhere would probably help.

Np. Wish I could offer more assistance..

Chad

test/CodeGen/AArch64/cmpxchg-O0.ll

76

Please add a new line.

[ab]

This makes sense to me, but:

Handle the expanded @llvm.aarch64.ldxr/stxr intrinsics to do away with any vregs (so fast-regalloc can't botch them), either in DAG or FastISel. I tried both, but the IR comparison always creates more. No change.

I don't understand: what "IR comparison"? If it worked, this seems to me like the ideal solution.

lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp

604–605

MBB.addSuccessor(LoadCmpBB) ?

616

Use a variable for MI.getDebugLoc(), perhaps?

640–641

Is this sufficient? What happens to a def inside MBB used in DoneBB?

My MI-fu is weak, and I don't recall ever seeing code doing this when splicing MBBs (a quick grep confirms that), so I might be missing something obvious.

642

Should this also transferSuccessorsAndUpdatePHIs()?

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

2323

MF is already available in SelectionDAGISel.

lib/Target/AArch64/AArch64ISelLowering.cpp

10160

missing word: "to the,"

lib/Target/AArch64/AArch64InstrAtomics.td

380

mayLoad/mayStore here as well?

[ab]

lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp

642

On second thought, I guess this is late enough for transferSuccessors() to be sufficient.

[t.p.northover]

Thanks for taking a look Ahmed.

[t.p.northover]

Think I've fixed most of the issues people mentioned.

[t.p.northover]

Ping?

[t.p.northover]

RePing?

Tim.

[ab]

There's still the live-in issue, but I'm not sure anyone cares after pseudo expansion. Quentin tells me you can use LivePhysRegs (::stepBackwards) to compute that for you.

Also, it occurs to me that nothing prevents a spill from being inserted with optimized regalloc. It's probably extremely unlikely, but maybe we should consider using the pseudo regardless of the opt level..

[ab]

(and sorry about the delay)

[t.p.northover]

New diff preserving MBB LiveIns during the transformation.

[ab]

Liveness in expandCMP_SWAP_128 as well?

With that, LGTM.

[t.p.northover]

Oops, well spotted. I've committed a fixed version as r266339. Thanks for reviewing.

Tim.

lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp

 // pass should be run after register allocation but before the post-regalloc
 // scheduling pass.
 //
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/AArch64AddressingModes.h"
 #include "AArch64InstrInfo.h"
 #include "AArch64Subtarget.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/Support/MathExtras.h"
 using namespace llvm;
 
 namespace llvm {
 void initializeAArch64ExpandPseudoPass(PassRegistry &);
 }
public:
   bool runOnMachineFunction(MachineFunction &Fn) override;
 
   const char *getPassName() const override {
     return AARCH64_EXPAND_PSEUDO_NAME;
   }
 
 private:
   bool expandMBB(MachineBasicBlock &MBB);
-  bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI);
+  bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
+                MachineBasicBlock::iterator &NextMBBI);
   bool expandMOVImm(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                     unsigned BitSize);
+
+  bool expandCMP_SWAP(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
+                      unsigned LdarOp, unsigned StlrOp, unsigned CmpOp,
+                      unsigned ExtendImm, unsigned ZeroReg,
+                      MachineBasicBlock::iterator &NextMBBI);
+  bool expandCMP_SWAP_128(MachineBasicBlock &MBB,
+                          MachineBasicBlock::iterator MBBI,
+                          MachineBasicBlock::iterator &NextMBBI);
 };
 char AArch64ExpandPseudo::ID = 0;
 }
 
 INITIALIZE_PASS(AArch64ExpandPseudo, "aarch64-expand-pseudo",
                 AARCH64_EXPAND_PSEUDO_NAME, false, false)
 
 /// \brief Transfer implicit operands on the pseudo instruction to the
MIB2 = BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(Opc))
                .addImm(AArch64_AM::getShifterImm(AArch64_AM::LSL, Shift));
   }
 
   transferImpOps(MI, MIB1, MIB2);
   MI.eraseFromParent();
   return true;
 }
 
+void addPostLoopLiveIns(MachineBasicBlock *MBB, LivePhysRegs &LiveRegs) {
+  for (auto I = LiveRegs.begin(); I != LiveRegs.end(); ++I)
+    MBB->addLiveIn(*I);
+}
+
+bool AArch64ExpandPseudo::expandCMP_SWAP(
+    MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, unsigned LdarOp,
+    unsigned StlrOp, unsigned CmpOp, unsigned ExtendImm, unsigned ZeroReg,
+    MachineBasicBlock::iterator &NextMBBI) {
+  MachineInstr &MI = *MBBI;
+  DebugLoc DL = MI.getDebugLoc();
+  MachineOperand &Dest = MI.getOperand(0);
+  unsigned StatusReg = MI.getOperand(1).getReg();
+  MachineOperand &Addr = MI.getOperand(2);
+  MachineOperand &Desired = MI.getOperand(3);
+  MachineOperand &New = MI.getOperand(4);
+
+  LivePhysRegs LiveRegs(&TII->getRegisterInfo());
+  LiveRegs.addLiveOuts(&MBB);
+  for (auto I = std::prev(MBB.end()); I != MBBI; --I)
+    LiveRegs.stepBackward(*I);
+
+  MachineFunction *MF = MBB.getParent();
+  auto LoadCmpBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
+  auto StoreBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
+  auto DoneBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
+
+  MF->insert(++MBB.getIterator(), LoadCmpBB);
+  MF->insert(++LoadCmpBB->getIterator(), StoreBB);
+  MF->insert(++StoreBB->getIterator(), DoneBB);
+
+  // .Lloadcmp:
+  //     ldaxr xDest, [xAddr]
+  //     cmp xDest, xDesired
+  //     b.ne .Ldone
+  MBB.addSuccessor(LoadCmpBB);
+  LoadCmpBB->addLiveIn(Addr.getReg());
+  LoadCmpBB->addLiveIn(Dest.getReg());
+  LoadCmpBB->addLiveIn(Desired.getReg());
+  addPostLoopLiveIns(LoadCmpBB, LiveRegs);
+
+  BuildMI(LoadCmpBB, DL, TII->get(LdarOp), Dest.getReg())
+      .addReg(Addr.getReg());
+  BuildMI(LoadCmpBB, DL, TII->get(CmpOp), ZeroReg)
+      .addReg(Dest.getReg(), getKillRegState(Dest.isDead()))
+      .addOperand(Desired)
+      .addImm(ExtendImm);
+  BuildMI(LoadCmpBB, DL, TII->get(AArch64::Bcc))
+      .addImm(AArch64CC::NE)
+      .addMBB(DoneBB)
+      .addReg(AArch64::NZCV, RegState::Implicit | RegState::Kill);
+  LoadCmpBB->addSuccessor(DoneBB);
+  LoadCmpBB->addSuccessor(StoreBB);
+
+  // .Lstore:
+  //     stlxr wStatus, xNew, [xAddr]
+  //     cbnz wStatus, .Lloadcmp
+  StoreBB->addLiveIn(Addr.getReg());
+  StoreBB->addLiveIn(New.getReg());
+  addPostLoopLiveIns(StoreBB, LiveRegs);
+
+  BuildMI(StoreBB, DL, TII->get(StlrOp), StatusReg)
+      .addOperand(New)
+      .addOperand(Addr);
+  BuildMI(StoreBB, DL, TII->get(AArch64::CBNZW))
+      .addReg(StatusReg, RegState::Kill)
+      .addMBB(LoadCmpBB);
+  StoreBB->addSuccessor(LoadCmpBB);
+  StoreBB->addSuccessor(DoneBB);
+
+  DoneBB->splice(DoneBB->end(), &MBB, MI, MBB.end());
+  DoneBB->transferSuccessors(&MBB);
+  addPostLoopLiveIns(DoneBB, LiveRegs);
+
+  NextMBBI = MBB.end();
+  MI.eraseFromParent();
+  return true;
+}
+
+bool AArch64ExpandPseudo::expandCMP_SWAP_128(
+    MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
+    MachineBasicBlock::iterator &NextMBBI) {
+
+  MachineInstr &MI = *MBBI;
+  DebugLoc DL = MI.getDebugLoc();
+  MachineOperand &DestLo = MI.getOperand(0);
+  MachineOperand &DestHi = MI.getOperand(1);
+  unsigned StatusReg = MI.getOperand(2).getReg();
+  MachineOperand &Addr = MI.getOperand(3);
+  MachineOperand &DesiredLo = MI.getOperand(4);
+  MachineOperand &DesiredHi = MI.getOperand(5);
+  MachineOperand &NewLo = MI.getOperand(6);
+  MachineOperand &NewHi = MI.getOperand(7);
+
+  MachineFunction *MF = MBB.getParent();
+  auto LoadCmpBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
+  auto StoreBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
+  auto DoneBB = MF->CreateMachineBasicBlock(MBB.getBasicBlock());
+
+  MF->insert(++MBB.getIterator(), LoadCmpBB);
+  MF->insert(++LoadCmpBB->getIterator(), StoreBB);
+  MF->insert(++StoreBB->getIterator(), DoneBB);
+
+  // .Lloadcmp:
+  //     ldaxp xDestLo, xDestHi, [xAddr]
+  //     cmp xDestLo, xDesiredLo
+  //     sbcs xDestHi, xDesiredHi
+  //     b.ne .Ldone
+  MBB.addSuccessor(LoadCmpBB);
+  LoadCmpBB->addLiveIn(Addr.getReg());
+  LoadCmpBB->addLiveIn(DestLo.getReg());
+  LoadCmpBB->addLiveIn(DestHi.getReg());
+  LoadCmpBB->addLiveIn(DesiredLo.getReg());
+  LoadCmpBB->addLiveIn(DesiredHi.getReg());
+  BuildMI(LoadCmpBB, DL, TII->get(AArch64::LDAXPX))
+      .addReg(DestLo.getReg(), RegState::Define)
+      .addReg(DestHi.getReg(), RegState::Define)
+      .addReg(Addr.getReg());
+  BuildMI(LoadCmpBB, DL, TII->get(AArch64::SUBSXrs), AArch64::XZR)
+      .addReg(DestLo.getReg(), getKillRegState(DestLo.isDead()))
+      .addOperand(DesiredLo)
+      .addImm(0);
+  BuildMI(LoadCmpBB, DL, TII->get(AArch64::SBCSXr), AArch64::XZR)
+      .addReg(DestHi.getReg(), getKillRegState(DestHi.isDead()))
+      .addOperand(DesiredHi);
+  BuildMI(LoadCmpBB, DL, TII->get(AArch64::Bcc))
+      .addImm(AArch64CC::NE)
+      .addMBB(DoneBB)
+      .addReg(AArch64::NZCV, RegState::Implicit | RegState::Kill);
+  LoadCmpBB->addSuccessor(DoneBB);
+  LoadCmpBB->addSuccessor(StoreBB);
+
+  // .Lstore:
+  //     stlxp wStatus, xNewLo, xNewHi, [xAddr]
+  //     cbnz wStatus, .Lloadcmp
+  StoreBB->addLiveIn(Addr.getReg());
+  StoreBB->addLiveIn(NewLo.getReg());
+  StoreBB->addLiveIn(NewHi.getReg());
+  BuildMI(StoreBB, DL, TII->get(AArch64::STLXPX), StatusReg)
+      .addOperand(NewLo)
+      .addOperand(NewHi)
+      .addOperand(Addr);
+  BuildMI(StoreBB, DL, TII->get(AArch64::CBNZW))
+      .addReg(StatusReg, RegState::Kill)
+      .addMBB(LoadCmpBB);
+  StoreBB->addSuccessor(LoadCmpBB);
+  StoreBB->addSuccessor(DoneBB);
+
+  DoneBB->splice(DoneBB->end(), &MBB, MI, MBB.end());
+  DoneBB->transferSuccessors(&MBB);
+
+  NextMBBI = MBB.end();
+  MI.eraseFromParent();
+  return true;
+}
+
 /// \brief If MBBI references a pseudo instruction that should be expanded here,
 /// do the expansion and return true.  Otherwise return false.
 bool AArch64ExpandPseudo::expandMI(MachineBasicBlock &MBB,
-                                 MachineBasicBlock::iterator MBBI) {
+                                   MachineBasicBlock::iterator MBBI,
+                                   MachineBasicBlock::iterator &NextMBBI) {
   MachineInstr &MI = *MBBI;
   unsigned Opcode = MI.getOpcode();
   switch (Opcode) {
   default:
     break;
 
   case AArch64::ADDWrr:
   case AArch64::SUBWrr:
bool AArch64ExpandPseudo::expandMI(MachineBasicBlock &MBB,
   case AArch64::RET_ReallyLR: {
     MachineInstrBuilder MIB =
         BuildMI(MBB, MBBI, MI.getDebugLoc(), TII->get(AArch64::RET))
           .addReg(AArch64::LR);
     transferImpOps(MI, MIB, MIB);
     MI.eraseFromParent();
     return true;
   }
+  case AArch64::CMP_SWAP_8:
+    return expandCMP_SWAP(MBB, MBBI, AArch64::LDAXRB, AArch64::STLXRB,
+                          AArch64::SUBSWrx,
+                          AArch64_AM::getArithExtendImm(AArch64_AM::UXTB, 0),
+                          AArch64::WZR, NextMBBI);
+  case AArch64::CMP_SWAP_16:
+    return expandCMP_SWAP(MBB, MBBI, AArch64::LDAXRH, AArch64::STLXRH,
+                          AArch64::SUBSWrx,
+                          AArch64_AM::getArithExtendImm(AArch64_AM::UXTH, 0),
+                          AArch64::WZR, NextMBBI);
+  case AArch64::CMP_SWAP_32:
+    return expandCMP_SWAP(MBB, MBBI, AArch64::LDAXRW, AArch64::STLXRW,
+                          AArch64::SUBSWrs,
+                          AArch64_AM::getShifterImm(AArch64_AM::LSL, 0),
+                          AArch64::WZR, NextMBBI);
+  case AArch64::CMP_SWAP_64:
+    return expandCMP_SWAP(MBB, MBBI,
+                          AArch64::LDAXRX, AArch64::STLXRX, AArch64::SUBSXrs,
+                          AArch64_AM::getShifterImm(AArch64_AM::LSL, 0),
+                          AArch64::XZR, NextMBBI);
+  case AArch64::CMP_SWAP_128:
+    return expandCMP_SWAP_128(MBB, MBBI, NextMBBI);
   }
   return false;
 }
 
 /// \brief Iterate over the instructions in basic block MBB and expand any
 /// pseudo instructions.  Return true if anything was modified.
 bool AArch64ExpandPseudo::expandMBB(MachineBasicBlock &MBB) {
   bool Modified = false;
 
   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
   while (MBBI != E) {
     MachineBasicBlock::iterator NMBBI = std::next(MBBI);
-    Modified |= expandMI(MBB, MBBI);
+    Modified |= expandMI(MBB, MBBI, NMBBI);
     MBBI = NMBBI;
   }
 
   return Modified;
 }
 
 bool AArch64ExpandPseudo::runOnMachineFunction(MachineFunction &MF) {
   TII = static_cast<const AArch64InstrInfo *>(MF.getSubtarget().getInstrInfo());

lib/Target/AArch64/AArch64ISelDAGToDAG.cpp

bool SelectExtendedSHL(SDValue N, unsigned Size, bool WantExtend,
                          SDValue &Offset, SDValue &SignExtend);
 
   template<unsigned RegWidth>
   bool SelectCVTFixedPosOperand(SDValue N, SDValue &FixedPos) {
     return SelectCVTFixedPosOperand(N, FixedPos, RegWidth);
   }
 
   bool SelectCVTFixedPosOperand(SDValue N, SDValue &FixedPos, unsigned Width);
+
+  void SelectCMP_SWAP(SDNode *N);
+
 };
 } // end anonymous namespace
 
 /// isIntImmediate - This method tests to see if the node is a constant
 /// operand. If so Imm will receive the 32-bit value.
 static bool isIntImmediate(const SDNode *N, uint64_t &Imm) {
   if (const ConstantSDNode *C = dyn_cast<const ConstantSDNode>(N)) {
     Imm = C->getZExtValue();
SDNode *AArch64DAGToDAGISel::SelectWriteRegister(SDNode *N) {
   if (IsValidSpecialReg)
     return CurDAG->getMachineNode(AArch64::MSR, DL, MVT::Other,
                                   CurDAG->getTargetConstant(Reg, DL, MVT::i32),
                                   N->getOperand(2), N->getOperand(0));
 
   return nullptr;
 }
 
+/// We've got special pseudo-instructions for these
+void AArch64DAGToDAGISel::SelectCMP_SWAP(SDNode *N) {
+  unsigned Opcode;
+  EVT MemTy = cast<MemSDNode>(N)->getMemoryVT();
+  if (MemTy == MVT::i8)
+    Opcode = AArch64::CMP_SWAP_8;
+  else if (MemTy == MVT::i16)
+    Opcode = AArch64::CMP_SWAP_16;
+  else if (MemTy == MVT::i32)
+    Opcode = AArch64::CMP_SWAP_32;
+  else if (MemTy == MVT::i64)
+    Opcode = AArch64::CMP_SWAP_64;
+  else
+    llvm_unreachable("Unknown AtomicCmpSwap type");
+
+  MVT RegTy = MemTy == MVT::i64 ? MVT::i64 : MVT::i32;
+  SDValue Ops[] = {N->getOperand(1), N->getOperand(2), N->getOperand(3),
+                   N->getOperand(0)};
+  SDNode *CmpSwap = CurDAG->getMachineNode(
+      Opcode, SDLoc(N),
+      CurDAG->getVTList(RegTy, MVT::i32, MVT::Other), Ops);
+
+  MachineSDNode::mmo_iterator MemOp = MF->allocateMemRefsArray(1);
+  MemOp[0] = cast<MemSDNode>(N)->getMemOperand();
+  cast<MachineSDNode>(CmpSwap)->setMemRefs(MemOp, MemOp + 1);
+
+  ReplaceUses(SDValue(N, 0), SDValue(CmpSwap, 0));
+  ReplaceUses(SDValue(N, 1), SDValue(CmpSwap, 2));
+}
+
 SDNode *AArch64DAGToDAGISel::Select(SDNode *Node) {
   // Dump information about the Node being selected
   DEBUG(errs() << "Selecting: ");
   DEBUG(Node->dump(CurDAG));
   DEBUG(errs() << "\n");
 
   // If we have a custom node, we already have selected!
   if (Node->isMachineOpcode()) {
     DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
     Node->setNodeId(-1);
     return nullptr;
   }
 
   // Few custom selection stuff.
   SDNode *ResNode = nullptr;
   EVT VT = Node->getValueType(0);
 
   switch (Node->getOpcode()) {
   default:
     break;
 
+  case ISD::ATOMIC_CMP_SWAP:
+    SelectCMP_SWAP(Node);
+    return nullptr;
+
   case ISD::READ_REGISTER:
     if (SDNode *Res = SelectReadRegister(Node))
       return Res;
     break;
 
   case ISD::WRITE_REGISTER:
     if (SDNode *Res = SelectWriteRegister(Node))
       return Res;

lib/Target/AArch64/AArch64ISelLowering.cpp

for (MVT Ty : {MVT::f32, MVT::f64}) {
     setOperationAction(ISD::FMINNUM, Ty, Legal);
     setOperationAction(ISD::FMAXNUM, Ty, Legal);
     setOperationAction(ISD::FMINNAN, Ty, Legal);
     setOperationAction(ISD::FMAXNAN, Ty, Legal);
   }
 
   setOperationAction(ISD::PREFETCH, MVT::Other, Custom);
 
+  setOperationAction(ISD::ATOMIC_CMP_SWAP, MVT::i128, Custom);
+
   // Lower READCYCLECOUNTER using an mrs from PMCCNTR_EL0.
   // This requires the Performance Monitors extension.
   if (Subtarget->hasPerfMon())
     setOperationAction(ISD::READCYCLECOUNTER, MVT::i64, Legal);
 
   if (Subtarget->isTargetMachO()) {
     // For iOS, we don't want to the normal expansion of a libcall to
     // sincos. We want to issue a libcall to __sincos_stret to avoid memory
static void ReplaceReductionResults(SDNode *N,
   SDLoc dl(N);
   std::tie(LoVT, HiVT) = DAG.GetSplitDestVTs(N->getValueType(0));
   std::tie(Lo, Hi) = DAG.SplitVectorOperand(N, 0);
   SDValue InterVal = DAG.getNode(InterOp, dl, LoVT, Lo, Hi);
   SDValue SplitVal = DAG.getNode(AcrossOp, dl, LoVT, InterVal);
   Results.push_back(SplitVal);
 }
 
+static void ReplaceCMP_SWAP_128Results(SDNode *N,
+                                       SmallVectorImpl<SDValue> & Results,
+                                       SelectionDAG &DAG) {
+  assert(N->getValueType(0) == MVT::i128 &&
+         "AtomicCmpSwap on types less than 128 should be legal");
+  SDValue Ops[] = {N->getOperand(1),
+                   N->getOperand(2)->getOperand(0),
+                   N->getOperand(2)->getOperand(1),
+                   N->getOperand(3)->getOperand(0),
+                   N->getOperand(3)->getOperand(1),
+                   N->getOperand(0)};
+  SDNode *CmpSwap = DAG.getMachineNode(
+      AArch64::CMP_SWAP_128, SDLoc(N),
+      DAG.getVTList(MVT::i64, MVT::i64, MVT::i32, MVT::Other), Ops);
+
+  MachineFunction &MF = DAG.getMachineFunction();
+  MachineSDNode::mmo_iterator MemOp = MF.allocateMemRefsArray(1);
+  MemOp[0] = cast<MemSDNode>(N)->getMemOperand();
+  cast<MachineSDNode>(CmpSwap)->setMemRefs(MemOp, MemOp + 1);
+
+  Results.push_back(SDValue(CmpSwap, 0));
+  Results.push_back(SDValue(CmpSwap, 1));
+  Results.push_back(SDValue(CmpSwap, 3));
+}
+
 void AArch64TargetLowering::ReplaceNodeResults(
     SDNode *N, SmallVectorImpl<SDValue> &Results, SelectionDAG &DAG) const {
   switch (N->getOpcode()) {
   default:
     llvm_unreachable("Don't know how to custom expand this");
   case ISD::BITCAST:
     ReplaceBITCASTResults(N, Results, DAG);
     return;
void AArch64TargetLowering::ReplaceNodeResults(
   case AArch64ISD::UMAXV:
     ReplaceReductionResults(N, Results, DAG, ISD::UMAX, AArch64ISD::UMAXV);
     return;
   case ISD::FP_TO_UINT:
   case ISD::FP_TO_SINT:
     assert(N->getValueType(0) == MVT::i128 && "unexpected illegal conversion");
     // Let normal code take care of it by not adding anything to Results.
     return;
+  case ISD::ATOMIC_CMP_SWAP:
+    ReplaceCMP_SWAP_128Results(N, Results, DAG);
+    return;
   }
 }
 
 bool AArch64TargetLowering::useLoadStackGuardNode() const {
   return true;
 }
 
 unsigned AArch64TargetLowering::combineRepeatedFPDivisors() const {

 TargetLowering::AtomicExpansionKind
 AArch64TargetLowering::shouldExpandAtomicRMWInIR(AtomicRMWInst *AI) const {
   unsigned Size = AI->getType()->getPrimitiveSizeInBits();
   return Size <= 128 ? AtomicExpansionKind::LLSC : AtomicExpansionKind::None;
 }
 
 bool AArch64TargetLowering::shouldExpandAtomicCmpXchgInIR(
     AtomicCmpXchgInst *AI) const {
-  return true;
+  // At -O0, fast-regalloc cannot cope with the live vregs necessary to
+  // implement cmpxchg without spilling. If the address being exchanged is also
+  // on the stack and close enough to the spill slot, this can lead to a
+  // situation where the monitor always gets cleared and the atomic operation
+  // can never succeed. So at -O0 we need a late-expanded pseudo-inst instead.
+  return getTargetMachine().getOptLevel() != 0;
 }
 
 Value *AArch64TargetLowering::emitLoadLinked(IRBuilder<> &Builder, Value *Addr,
                                              AtomicOrdering Ord) const {
   Module *M = Builder.GetInsertBlock()->getParent()->getParent();
   Type *ValTy = cast<PointerType>(Addr->getType())->getElementType();
   bool IsAcquire = isAtLeastAcquire(Ord);
 

lib/Target/AArch64/AArch64InstrAtomics.td

def : Pat<(stlxr_2 (and GPR64:$val, 0xffff), GPR64sp:$addr),
           (STLXRH (EXTRACT_SUBREG GPR64:$val, sub_32), GPR64sp:$addr)>;
 def : Pat<(stlxr_4 (and GPR64:$val, 0xffffffff), GPR64sp:$addr),
           (STLXRW (EXTRACT_SUBREG GPR64:$val, sub_32), GPR64sp:$addr)>;
 
 
 // And clear exclusive.
 
 def : Pat<(int_aarch64_clrex), (CLREX 0xf)>;
+
+//===----------------------------------
+// Atomic cmpxchg for -O0
+//===----------------------------------
+
+// The fast register allocator used during -O0 inserts spills to cover any VRegs
+// live across basic block boundaries. When this happens between an LDXR and an
+// STXR it can clear the exclusive monitor, causing all cmpxchg attempts to
+// fail.
+
+// Unfortunately, this means we have to have an alternative (expanded
+// post-regalloc) path for -O0 compilations. Fortunately this path can be
+// significantly more naive than the standard expansion: we conservatively
+// assume seq_cst, strong cmpxchg and omit clrex on failure.
+
+let Constraints = "@earlyclobber $Rd,@earlyclobber $status",
+    mayLoad = 1, mayStore = 1 in {
+def CMP_SWAP_8 : Pseudo<(outs GPR32:$Rd, GPR32:$status),
+                        (ins GPR64:$addr, GPR32:$desired, GPR32:$new), []>,
+                 Sched<[WriteAtomic]>;
+
+def CMP_SWAP_16 : Pseudo<(outs GPR32:$Rd, GPR32:$status),
+                         (ins GPR64:$addr, GPR32:$desired, GPR32:$new), []>,
+                  Sched<[WriteAtomic]>;
+
+def CMP_SWAP_32 : Pseudo<(outs GPR32:$Rd, GPR32:$status),
+                         (ins GPR64:$addr, GPR32:$desired, GPR32:$new), []>,
+                  Sched<[WriteAtomic]>;
+
+def CMP_SWAP_64 : Pseudo<(outs GPR64:$Rd, GPR32:$status),
+                         (ins GPR64:$addr, GPR64:$desired, GPR64:$new), []>,
+                  Sched<[WriteAtomic]>;
+}
+
+let Constraints = "@earlyclobber $RdLo,@earlyclobber $RdHi,@earlyclobber $status",
+    mayLoad = 1, mayStore = 1 in
+def CMP_SWAP_128 : Pseudo<(outs GPR64:$RdLo, GPR64:$RdHi, GPR32:$status),
+                          (ins GPR64:$addr, GPR64:$desiredLo, GPR64:$desiredHi,
+                               GPR64:$newLo, GPR64:$newHi), []>,
+                   Sched<[WriteAtomic]>;

test/CodeGen/AArch64/cmpxchg-O0.ll

+; RUN: llc -mtriple=aarch64-linux-gnu -O0 %s -o - | FileCheck %s
+
+define { i8, i1 } @test_cmpxchg_8(i8* %addr, i8 %desired, i8 %new) nounwind {
+; CHECK-LABEL: test_cmpxchg_8:
+; CHECK: [[RETRY:.LBB[0-9]+_[0-9]+]]:
+; CHECK:     ldaxrb [[OLD:w[0-9]+]], [x0]
+; CHECK:     cmp [[OLD]], w1, uxtb
+; CHECK:     b.ne [[DONE:.LBB[0-9]+_[0-9]+]]
+; CHECK:     stlxrb [[STATUS:w[3-9]]], w2, [x0]
+; CHECK:     cbnz [[STATUS]], [[RETRY]]
+; CHECK: [[DONE]]:
+; CHECK:     subs {{w[0-9]+}}, [[OLD]], w1
+; CHECK:     cset {{w[0-9]+}}, eq
+  %res = cmpxchg i8* %addr, i8 %desired, i8 %new seq_cst monotonic
+  ret { i8, i1 } %res
+}
+
+define { i16, i1 } @test_cmpxchg_16(i16* %addr, i16 %desired, i16 %new) nounwind {
+; CHECK-LABEL: test_cmpxchg_16:
+; CHECK: [[RETRY:.LBB[0-9]+_[0-9]+]]:
+; CHECK:     ldaxrh [[OLD:w[0-9]+]], [x0]
+; CHECK:     cmp [[OLD]], w1, uxth
+; CHECK:     b.ne [[DONE:.LBB[0-9]+_[0-9]+]]
+; CHECK:     stlxrh [[STATUS:w[3-9]]], w2, [x0]
+; CHECK:     cbnz [[STATUS]], [[RETRY]]
+; CHECK: [[DONE]]:
+; CHECK:     subs {{w[0-9]+}}, [[OLD]], w1
+; CHECK:     cset {{w[0-9]+}}, eq
+  %res = cmpxchg i16* %addr, i16 %desired, i16 %new seq_cst monotonic
+  ret { i16, i1 } %res
+}
+
+define { i32, i1 } @test_cmpxchg_32(i32* %addr, i32 %desired, i32 %new) nounwind {
+; CHECK-LABEL: test_cmpxchg_32:
+; CHECK: [[RETRY:.LBB[0-9]+_[0-9]+]]:
+; CHECK:     ldaxr [[OLD:w[0-9]+]], [x0]
+; CHECK:     cmp [[OLD]], w1
+; CHECK:     b.ne [[DONE:.LBB[0-9]+_[0-9]+]]
+; CHECK:     stlxr [[STATUS:w[3-9]]], w2, [x0]
+; CHECK:     cbnz [[STATUS]], [[RETRY]]
+; CHECK: [[DONE]]:
+; CHECK:     subs {{w[0-9]+}}, [[OLD]], w1
+; CHECK:     cset {{w[0-9]+}}, eq
+  %res = cmpxchg i32* %addr, i32 %desired, i32 %new seq_cst monotonic
+  ret { i32, i1 } %res
+}
+
+define { i64, i1 } @test_cmpxchg_64(i64* %addr, i64 %desired, i64 %new) nounwind {
+; CHECK-LABEL: test_cmpxchg_64:
+; CHECK: [[RETRY:.LBB[0-9]+_[0-9]+]]:
+; CHECK:     ldaxr [[OLD:x[0-9]+]], [x0]
+; CHECK:     cmp [[OLD]], x1
+; CHECK:     b.ne [[DONE:.LBB[0-9]+_[0-9]+]]
+; CHECK:     stlxr [[STATUS:w[3-9]]], x2, [x0]
+; CHECK:     cbnz [[STATUS]], [[RETRY]]
+; CHECK: [[DONE]]:
+; CHECK:     subs {{x[0-9]+}}, [[OLD]], x1
+; CHECK:     cset {{w[0-9]+}}, eq
+  %res = cmpxchg i64* %addr, i64 %desired, i64 %new seq_cst monotonic
+  ret { i64, i1 } %res
+}
+
+define { i128, i1 } @test_cmpxchg_128(i128* %addr, i128 %desired, i128 %new) nounwind {
+; CHECK-LABEL: test_cmpxchg_128:
+; CHECK: [[RETRY:.LBB[0-9]+_[0-9]+]]:
+; CHECK:     ldaxp [[OLD_LO:x[0-9]+]], [[OLD_HI:x[0-9]+]], [x0]
+; CHECK:     cmp [[OLD_LO]], x2
+; CHECK:     sbcs xzr, [[OLD_HI]], x3
+; CHECK:     b.ne [[DONE:.LBB[0-9]+_[0-9]+]]
+; CHECK:     stlxp [[STATUS:w[0-9]+]], x4, x5, [x0]
+; CHECK:     cbnz [[STATUS]], [[RETRY]]
+; CHECK: [[DONE]]:
+  %res = cmpxchg i128* %addr, i128 %desired, i128 %new seq_cst monotonic
+  ret { i128, i1 } %res
+}