[AArch64] Reduce number of callee-save save/restores.

[gberry]

Summary

Before this change, callee-save registers would be rounded up to even
pairs of GPRs and FPRs. This change eliminates these extra padding
load/stores, though it does keep the stack allocation the same size
unless both the GPR and FPR sets have an odd size, in which case one
full pair stack slot (16 bytes) is saved.

[t.p.northover]

Hi Geoff,

Unfortunately this has implications for exception unwinding on iOS. We have fast-path .debug_frame equivalents that only have 32 bits to store the prologue's format, and the format assumes the registers are stored in pairs.

On the other hand, we really don't want frame lowering to be any more complex than it absolutely has to be. For now, we probably have to go with the existing format on Darwin but I think we can probably come up with a better determineCalleeSaves that serves both needs.

To start with, some observations (none of them your fault, the existing code did it):

• UnspilledCSFPRs is completely unused.
• Only one value is really needed in UnspilledCSGPRs: we need one to scavenge, but that's it.
• Only the sum of NumGPRSpilled and NumFPRSpilled is used.

So, I think we can rewrite the top loop as:

// Figure out which callee-saved registers to save/restore.
for (unsigned i = 0; CSRegs[i]; ++i) {
  const unsigned Reg = CSRegs[i];
  bool RegUsed = SavedRegs.test(Reg);

  if (!RegUsed && AArch64::GPR64RegClass.contains(Reg) && !RegInfo->isReservedReg(MF, Reg)) {
    // Save this one for later in case we need a scratch register.
    UnspilledGPR = Reg;
    continue;
  }

  // MachO's compact unwind format relies on all registers being stored in pairs.
  // FIXME: the usual format is actually better if unwinding isn't needed.
  unsigned PairedReg = CSRegs[i ^ 1];
  if (MF.getSubtarget().isTargetMachO() && !SavedRegs.test(PairedReg)) {
    SavedRegs.set(PairedReg);
    ExtraCSSpill = true;
  }
}

NumRegsSpilled = SavedRegs.size();
CanEliminateFrame = NumRegsSpilled == 0;

Do you think you could make something like that work, or have I overlooked a key use that brings my whole edifice crumbling down?

Cheers.

Tim.

lib/Target/AArch64/AArch64FrameLowering.cpp

746

I think this should be asserting 16: it matches the comment a few lines above, the corresponding set call, and the ABI requirement.

[t.p.northover]

Oh, and the debug printing can probably be a lambda'd-up std::for_each or similar to avoid complicating the control flow of the loop further.

[t.p.northover]

NumRegsSpilled = SavedRegs.size();

Sorry, that would definitely be .count() if the loop's at all viable.

Tim,

[gberry]

Tim,

Thanks, this is the kind of thing I suspected was probably hiding out there. I assume these MachO fast unwind restrictions also would prevent doing non-leaf frame pointer elimination and redzone optimization? Do you think these restrictions are currently captured in the tests that I modified? Perhaps some of these tests need another non apple triple run/check so we cover both paths?

[t.p.northover]

Hi Geoff,

I assume these MachO fast unwind restrictions also would prevent doing non-leaf frame pointer elimination and redzone optimization.

We'd probably want to keep non-leaf frame pointers independently of unwinding (people are very keen on getting good backtraces here). Similarly, we'd have to check our libc (etc) for red zone violations before it could be turned on.

Are you thinking of using the red zone for callee-saved registers too? That might have unwinding implications.

Do you think these restrictions are currently captured in the tests that I modified?

I think I should probably specifically write a few basic compact unwind codegen functions which would have broken with your patch. Just a sort of smokescreen to catch obvious things that should be using the compact format. I'll do that today (hopefully).

Cheers.

Tim.

[gberry]

Updated revision to deal with MachO unwind info issues.

[gberry]

Hi Tim,

I've uploaded a new version which should hopefully address the MachO unwind issues. I've tried to add more test coverage to the existing lit tests, but I think adding the MachO specific smoke tests would also be a good thing.

Thanks for the update regarding non-leaf frame pointer omission and red-zone usage. I'm still exploring the options at this point and just wanted to get any iOS specific requirements in my head early. The first step I'll take in this direction is probably just getting -fomit-frame-pointer to actually to work for non-leaf functions.

[t.p.northover]

Thanks for rewriting it to accommodate MachO. I've got a couple of minor suggestions, but only saw one likely bug (the unconditional register increment).

Cheers.

Tim.

lib/Target/AArch64/AArch64FrameLowering.cpp

697–702

Possibly:

assert(AArch64::GPR64RegClass.contains(RPI.Reg1) ||
       AArch64::FPR64RegClass.contains(RPI.Reg1));
RPI.IsGPR =  AArch64::GPR64RegClass.contains(RPI.Reg1);

746

Did you decide a stack size == 8 (mod 16) was allowed in some circumstances?

943

The logic would be marginally simpler if you set this unconditionally and then used the MachO test when actually using it.

981

This will be incremented even if UnspilledCSGPRPaired was already spilled.

[gberry]

Address Tim's comments.

[gberry]

lib/Target/AArch64/AArch64FrameLowering.cpp

746

Not currently, no. Maybe in a future change that combines the callee-save stack bump with the local variable stack bump.

981

Good catch. I just recalculated NumRegsSpilled at the end here so SavedRegs is always the canonical representation.

[t.p.northover]

lib/Target/AArch64/AArch64FrameLowering.cpp

746

I'm not sure that would be allowed. The AAPCS says "Additionally, at any point at which memory is accessed via SP, the hardware requires that SP mod 16 = 0. The stack must be quad-word aligned."

It's a bit more complicated than that (it's configurable via SCTLR), but I think we should force anyone who wants to weaken that to think very hard about it.

981

Ah, neat!

[gberry]

Thanks Tim. Are you okay with this going in, or should I wait for your additional test cases? I'm fine with either.

lib/Target/AArch64/AArch64FrameLowering.cpp

746

I don't think the hypothetical future change that I'm thinking of would violate that rule.
If there was only a single instruction bumping the SP (for both the callee-save area and the local variable area), then it would be okay if the callee-save area was not 16-byte aligned as long as the "hole" was filled by local variable data so the single SP bump was 16-byte aligned. There may be other reasons why this isn't workable though. I'm also not sure it's worth the effort.

[t.p.northover]

Yep, I think this is OK now. Thanks again for the updates!

Tim.

lib/Target/AArch64/AArch64FrameLowering.cpp

 
 struct RegPairInfo {
   RegPairInfo() : Reg1(AArch64::NoRegister), Reg2(AArch64::NoRegister) {}
   unsigned Reg1;
   unsigned Reg2;
   int FrameIdx;
   int Offset;
   bool IsGPR;
+  bool isPaired() const { return Reg2 != AArch64::NoRegister; }
 };
 
-static void
-computeCalleeSaveRegisterPairs(const std::vector<CalleeSavedInfo> &CSI,
-                               const TargetRegisterInfo *TRI,
-                               SmallVectorImpl<RegPairInfo> &RegPairs) {
+static void computeCalleeSaveRegisterPairs(
+    MachineFunction &MF, const std::vector<CalleeSavedInfo> &CSI,
+    const TargetRegisterInfo *TRI, SmallVectorImpl<RegPairInfo> &RegPairs) {
 
+  if (CSI.empty())
+    return;
+
+  AArch64FunctionInfo *AFI = MF.getInfo<AArch64FunctionInfo>();
+  MachineFrameInfo *MFI = MF.getFrameInfo();
   unsigned Count = CSI.size();
-  assert((Count & 1) == 0 && "Odd number of callee-saved regs to spill!");
+  unsigned Offset = AFI->getCalleeSavedStackSize();
 
-  for (unsigned i = 0; i < Count; i += 2) {
-    unsigned idx = Count - i - 2;
+  for (unsigned i = 0; i < Count; ++i) {
     RegPairInfo RPI;
-    RPI.Reg1 = CSI[idx].getReg();
-    RPI.Reg2 = CSI[idx + 1].getReg();
+    RPI.Reg1 = CSI[i].getReg();
+
+    if (AArch64::GPR64RegClass.contains(RPI.Reg1))
+      RPI.IsGPR = true;
+    else if (AArch64::FPR64RegClass.contains(RPI.Reg1))
+      RPI.IsGPR = false;
+    else
+      llvm_unreachable("Unexpected callee saved register!");
+
+    // Add the next reg to the pair if it is in the same register class.
+    if (i + 1 < Count) {
+      unsigned NextReg = CSI[i + 1].getReg();
+      if ((RPI.IsGPR && AArch64::GPR64RegClass.contains(NextReg)) ||
+          (!RPI.IsGPR && AArch64::FPR64RegClass.contains(NextReg)))
+        RPI.Reg2 = NextReg;
+    }
 
     // GPRs and FPRs are saved in pairs of 64-bit regs. We expect the CSI
     // list to come in sorted by frame index so that we can issue the store
     // pair instructions directly. Assert if we see anything otherwise.
     //
     // The order of the registers in the list is controlled by
     // getCalleeSavedRegs(), so they will always be in-order, as well.
-    assert(CSI[idx].getFrameIdx() + 1 == CSI[idx + 1].getFrameIdx() &&
+    assert((!RPI.isPaired() ||
+            (CSI[i].getFrameIdx() + 1 == CSI[i + 1].getFrameIdx())) &&
            "Out of order callee saved regs!");
-    assert((Count & 1) == 0 && "Odd number of callee-saved regs to spill!");
-    assert((i & 1) == 0 && "Odd index for callee-saved reg spill!");
-    RPI.FrameIdx = CSI[idx + 1].getFrameIdx();
+    RPI.FrameIdx = CSI[i].getFrameIdx();
 
-    if (AArch64::GPR64RegClass.contains(RPI.Reg1))
-      RPI.IsGPR = true;
-    else if (AArch64::FPR64RegClass.contains(RPI.Reg1))
-      RPI.IsGPR = false;
-    else
-      llvm_unreachable("Unexpected callee saved register!");
-    // Compute offset: i = 0 => offset = Count;
-    //                 i = 2 => offset = -(Count - 2) + Count = 2 = i; etc.
-    RPI.Offset = (i == 0) ? Count : i;
+    if (Count * 8 != AFI->getCalleeSavedStackSize() && !RPI.isPaired()) {
+      // Round up size of non-pair to pair size if we need to pad the
+      // callee-save area to ensure 16-byte alignment.
+      Offset -= 16;
+      assert(MFI->getObjectAlignment(RPI.FrameIdx) <= 16);
+      MFI->setObjectSize(RPI.FrameIdx, 16);
+    } else
+      Offset -= RPI.isPaired() ? 16 : 8;
+    assert(Offset % 8 == 0);
+    RPI.Offset = Offset / 8;
     assert((RPI.Offset >= -64 && RPI.Offset <= 63) &&
            "Offset out of bounds for LDP/STP immediate");
 
     RegPairs.push_back(RPI);
+    if (RPI.isPaired())
+      ++i;
   }
+
+  // Align first offset to even 16-byte boundary to avoid additional SP
+  // adjustment instructions.
+  // Last pair offset is size of whole callee-save region for SP
+  // pre-dec/post-inc.
+  RegPairInfo &LastPair = RegPairs.back();
+  assert(AFI->getCalleeSavedStackSize() % 8 == 0);
+  LastPair.Offset = AFI->getCalleeSavedStackSize() / 8;
 }
 
 bool AArch64FrameLowering::spillCalleeSavedRegisters(
     MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
     const std::vector<CalleeSavedInfo> &CSI,
     const TargetRegisterInfo *TRI) const {
   MachineFunction &MF = *MBB.getParent();
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
   DebugLoc DL;
   SmallVector<RegPairInfo, 8> RegPairs;
 
-  computeCalleeSaveRegisterPairs(CSI, TRI, RegPairs);
+  computeCalleeSaveRegisterPairs(MF, CSI, TRI, RegPairs);
 
-  for (auto RPII = RegPairs.begin(), RPIE = RegPairs.end(); RPII != RPIE;
+  for (auto RPII = RegPairs.rbegin(), RPIE = RegPairs.rend(); RPII != RPIE;
        ++RPII) {
     RegPairInfo RPI = *RPII;
     unsigned Reg1 = RPI.Reg1;
     unsigned Reg2 = RPI.Reg2;
     unsigned StrOpc;
 
     // Issue sequence of non-sp increment and pi sp spills for cs regs. The
     // first spill is a pre-increment that allocates the stack.
     // For example:
     //    stp     x22, x21, [sp, #-48]!   // addImm(-6)
     //    stp     x20, x19, [sp, #16]    // addImm(+2)
     //    stp     fp, lr, [sp, #32]      // addImm(+4)
     // Rationale: This sequence saves uop updates compared to a sequence of
     // pre-increment spills like stp xi,xj,[sp,#-16]!
     // Note: Similar rationale and sequence for restores in epilog.
-    bool BumpSP = RPII == RegPairs.begin();
+    bool BumpSP = RPII == RegPairs.rbegin();
     if (RPI.IsGPR) {
       // For first spill use pre-increment store.
       if (BumpSP)
-        StrOpc = AArch64::STPXpre;
+        StrOpc = RPI.isPaired() ? AArch64::STPXpre : AArch64::STRXpre;
       else
-        StrOpc = AArch64::STPXi;
+        StrOpc = RPI.isPaired() ? AArch64::STPXi : AArch64::STRXui;
     } else {
       // For first spill use pre-increment store.
       if (BumpSP)
-        StrOpc = AArch64::STPDpre;
+        StrOpc = RPI.isPaired() ? AArch64::STPDpre : AArch64::STRDpre;
       else
-        StrOpc = AArch64::STPDi;
+        StrOpc = RPI.isPaired() ? AArch64::STPDi : AArch64::STRDui;
     }
-    DEBUG(dbgs() << "CSR spill: (" << TRI->getName(Reg1) << ", "
-                 << TRI->getName(Reg2) << ") -> fi#(" << RPI.FrameIdx
-                 << ", " << RPI.FrameIdx+1 << ")\n");
+    DEBUG(dbgs() << "CSR spill: (" << TRI->getName(Reg1);
+          if (RPI.isPaired())
+            dbgs() << ", " << TRI->getName(Reg2);
+          dbgs() << ") -> fi#(" << RPI.FrameIdx;
+          if (RPI.isPaired())
+            dbgs() << ", " << RPI.FrameIdx+1;
+          dbgs() << ")\n");
 
     const int Offset = BumpSP ? -RPI.Offset : RPI.Offset;
     MachineInstrBuilder MIB = BuildMI(MBB, MI, DL, TII.get(StrOpc));
     if (BumpSP)
       MIB.addReg(AArch64::SP, RegState::Define);
 
+    if (RPI.isPaired()) {
       MBB.addLiveIn(Reg1);
       MBB.addLiveIn(Reg2);
       MIB.addReg(Reg2, getPrologueDeath(MF, Reg2))
         .addReg(Reg1, getPrologueDeath(MF, Reg1))
         .addReg(AArch64::SP)
         .addImm(Offset) // [sp, #offset * 8], where factor * 8 is implicit
         .setMIFlag(MachineInstr::FrameSetup);
+    } else {
+      MBB.addLiveIn(Reg1);
+      MIB.addReg(Reg1, getPrologueDeath(MF, Reg1))
+        .addReg(AArch64::SP)
+        .addImm(BumpSP ? Offset * 8 : Offset) // pre-inc version is unscaled
+        .setMIFlag(MachineInstr::FrameSetup);
+    }
   }
   return true;
 }
 
 bool AArch64FrameLowering::restoreCalleeSavedRegisters(
     MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
     const std::vector<CalleeSavedInfo> &CSI,
     const TargetRegisterInfo *TRI) const {
   MachineFunction &MF = *MBB.getParent();
   const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo();
   DebugLoc DL;
   SmallVector<RegPairInfo, 8> RegPairs;
 
   if (MI != MBB.end())
     DL = MI->getDebugLoc();
 
-  computeCalleeSaveRegisterPairs(CSI, TRI, RegPairs);
+  computeCalleeSaveRegisterPairs(MF, CSI, TRI, RegPairs);
 
-  for (auto RPII = RegPairs.rbegin(), RPIE = RegPairs.rend(); RPII != RPIE;
+  for (auto RPII = RegPairs.begin(), RPIE = RegPairs.end(); RPII != RPIE;
        ++RPII) {
     RegPairInfo RPI = *RPII;
     unsigned Reg1 = RPI.Reg1;
     unsigned Reg2 = RPI.Reg2;
 
     // Issue sequence of non-sp increment and sp-pi restores for cs regs. Only
     // the last load is sp-pi post-increment and de-allocates the stack:
     // For example:
     //    ldp     fp, lr, [sp, #32]       // addImm(+4)
     //    ldp     x20, x19, [sp, #16]     // addImm(+2)
     //    ldp     x22, x21, [sp], #48     // addImm(+6)
     // Note: see comment in spillCalleeSavedRegisters()
     unsigned LdrOpc;
-    bool BumpSP = RPII == std::prev(RegPairs.rend());
+    bool BumpSP = RPII == std::prev(RegPairs.end());
     if (RPI.IsGPR) {
       if (BumpSP)
-        LdrOpc = AArch64::LDPXpost;
+        LdrOpc = RPI.isPaired() ? AArch64::LDPXpost : AArch64::LDRXpost;
       else
-        LdrOpc = AArch64::LDPXi;
+        LdrOpc = RPI.isPaired() ? AArch64::LDPXi : AArch64::LDRXui;
     } else {
       if (BumpSP)
-        LdrOpc = AArch64::LDPDpost;
+        LdrOpc = RPI.isPaired() ? AArch64::LDPDpost : AArch64::LDRDpost;
       else
-        LdrOpc = AArch64::LDPDi;
+        LdrOpc = RPI.isPaired() ? AArch64::LDPDi : AArch64::LDRDui;
     }
-    DEBUG(dbgs() << "CSR restore: (" << TRI->getName(Reg1) << ", "
-                 << TRI->getName(Reg2) << ") -> fi#(" << RPI.FrameIdx
-                 << ", " << RPI.FrameIdx+1 << ")\n");
+    DEBUG(dbgs() << "CSR restore: (" << TRI->getName(Reg1);
+          if (RPI.isPaired())
+            dbgs() << ", " << TRI->getName(Reg2);
+          dbgs() << ") -> fi#(" << RPI.FrameIdx;
+          if (RPI.isPaired())
+            dbgs() << ", " << RPI.FrameIdx+1;
+          dbgs() << ")\n");
 
     const int Offset = RPI.Offset;
     MachineInstrBuilder MIB = BuildMI(MBB, MI, DL, TII.get(LdrOpc));
     if (BumpSP)
       MIB.addReg(AArch64::SP, RegState::Define);
 
+    if (RPI.isPaired())
       MIB.addReg(Reg2, getDefRegState(true))
         .addReg(Reg1, getDefRegState(true))
         .addReg(AArch64::SP)
         .addImm(Offset) // [sp], #offset * 8  or [sp, #offset * 8]
                         // where the factor * 8 is implicit
         .setMIFlag(MachineInstr::FrameDestroy);
+    else
+      MIB.addReg(Reg1, getDefRegState(true))
+        .addReg(AArch64::SP)
+        .addImm(BumpSP ? Offset * 8 : Offset) // post-dec version is unscaled
+        .setMIFlag(MachineInstr::FrameDestroy);
   }
   return true;
 }
 
 void AArch64FrameLowering::determineCalleeSaves(MachineFunction &MF,
                                                 BitVector &SavedRegs,
                                                 RegScavenger *RS) const {
   // All calls are tail calls in GHC calling conv, and functions have no
void AArch64FrameLowering::determineCalleeSaves(MachineFunction &MF,
   // If any callee-saved registers are used, the frame cannot be eliminated.
   unsigned NumGPRSpilled = 0;
   unsigned NumFPRSpilled = 0;
   bool ExtraCSSpill = false;
   bool CanEliminateFrame = true;
   DEBUG(dbgs() << "*** determineCalleeSaves\nUsed CSRs:");
   const MCPhysReg *CSRegs = RegInfo->getCalleeSavedRegs(&MF);
 
-  // Check pairs of consecutive callee-saved registers.
-  for (unsigned i = 0; CSRegs[i]; i += 2) {
-    assert(CSRegs[i + 1] && "Odd number of callee-saved registers!");
-
-    const unsigned OddReg = CSRegs[i];
-    const unsigned EvenReg = CSRegs[i + 1];
-    assert((AArch64::GPR64RegClass.contains(OddReg) &&
-            AArch64::GPR64RegClass.contains(EvenReg)) ^
-               (AArch64::FPR64RegClass.contains(OddReg) &&
-                AArch64::FPR64RegClass.contains(EvenReg)) &&
-           "Register class mismatch!");
-
-    const bool OddRegUsed = SavedRegs.test(OddReg);
-    const bool EvenRegUsed = SavedRegs.test(EvenReg);
-
-    // Early exit if none of the registers in the register pair is actually
-    // used.
-    if (!OddRegUsed && !EvenRegUsed) {
-      if (AArch64::GPR64RegClass.contains(OddReg)) {
-        UnspilledCSGPRs.push_back(OddReg);
-        UnspilledCSGPRs.push_back(EvenReg);
-      } else {
-        UnspilledCSFPRs.push_back(OddReg);
-        UnspilledCSFPRs.push_back(EvenReg);
-      }
-      continue;
-    }
+  // Figure out which callee-saved registers to save/restore.
+  for (unsigned i = 0; CSRegs[i]; ++i) {
+    const unsigned Reg = CSRegs[i];
+    bool RegUsed = SavedRegs.test(Reg);
 
-    unsigned Reg = AArch64::NoRegister;
-    // If only one of the registers of the register pair is used, make sure to
-    // mark the other one as used as well.
-    if (OddRegUsed ^ EvenRegUsed) {
-      // Find out which register is the additional spill.
-      Reg = OddRegUsed ? EvenReg : OddReg;
-      SavedRegs.set(Reg);
+    if (AArch64::GPR64RegClass.contains(Reg)) {
+      if (RegUsed)
+        ++NumGPRSpilled;
+      else
+        UnspilledCSGPRs.push_back(Reg);
+    } else {
+      if (RegUsed)
+        ++NumFPRSpilled;
+      else
+        UnspilledCSFPRs.push_back(Reg);
     }
 
-    DEBUG(dbgs() << ' ' << PrintReg(OddReg, RegInfo));
-    DEBUG(dbgs() << ' ' << PrintReg(EvenReg, RegInfo));
+    if (!RegUsed)
+      continue;
 
-    assert(((OddReg == AArch64::LR && EvenReg == AArch64::FP) ||
-            (RegInfo->getEncodingValue(OddReg) + 1 ==
-             RegInfo->getEncodingValue(EvenReg))) &&
-           "Register pair of non-adjacent registers!");
-    if (AArch64::GPR64RegClass.contains(OddReg)) {
-      NumGPRSpilled += 2;
-      // If it's not a reserved register, we can use it in lieu of an
-      // emergency spill slot for the register scavenger.
-      // FIXME: It would be better to instead keep looking and choose another
-      // unspilled register that isn't reserved, if there is one.
-      if (Reg != AArch64::NoRegister && !RegInfo->isReservedReg(MF, Reg))
-        ExtraCSSpill = true;
-    } else
-      NumFPRSpilled += 2;
+    DEBUG(dbgs() << ' ' << PrintReg(Reg, RegInfo));
 
     CanEliminateFrame = false;
   }
   DEBUG(dbgs() << "\n");
 
   // FIXME: Set BigStack if any stack slot references may be out of range.
   // For now, just conservatively guestimate based on unscaled indexing
   // range. We'll end up allocating an unnecessary spill slot a lot, but
if (BigStack || !CanEliminateFrame || RegInfo->cannotEliminateFrame(MF))
     AFI->setHasStackFrame(true);
 
   // Estimate if we might need to scavenge a register at some point in order
   // to materialize a stack offset. If so, either spill one additional
   // callee-saved register or reserve a special spill slot to facilitate
   // register scavenging. If we already spilled an extra callee-saved register
   // above to keep the number of spills even, we don't need to do anything else
   // here.
-  if (BigStack && !ExtraCSSpill) {
+  if (BigStack) {
 
-    // If we're adding a register to spill here, we have to add two of them
-    // to keep the number of regs to spill even.
-    assert(((UnspilledCSGPRs.size() & 1) == 0) && "Odd number of registers!");
-    unsigned Count = 0;
-    while (!UnspilledCSGPRs.empty() && Count < 2) {
-      unsigned Reg = UnspilledCSGPRs.back();
-      UnspilledCSGPRs.pop_back();
+    for (auto RegI = UnspilledCSGPRs.rbegin(), RegE = UnspilledCSGPRs.rend();
+         RegI != RegE; ++RegI) {
+      unsigned Reg = *RegI;
+      if (!RegInfo->isReservedReg(MF, Reg)) {
         DEBUG(dbgs() << "Spilling " << PrintReg(Reg, RegInfo)
                      << " to get a scratch register.\n");
         SavedRegs.set(Reg);
         ExtraCSSpill = true;
-      ++Count;
         ++NumGPRSpilled;
+        UnspilledCSGPRs.erase(std::next(RegI).base());
+        break;
+      }
     }
 
     // If we didn't find an extra callee-saved register to spill, create
     // an emergency spill slot.
     if (!ExtraCSSpill) {
       const TargetRegisterClass *RC = &AArch64::GPR64RegClass;
       int FI = MFI->CreateStackObject(RC->getSize(), RC->getAlignment(), false);
       RS->addScavengingFrameIndex(FI);
       DEBUG(dbgs() << "No available CS registers, allocated fi#" << FI
                    << " as the emergency spill slot.\n");
     }
   }
 
-  AFI->setCalleeSavedStackSize(8 * (NumGPRSpilled + NumFPRSpilled));
+  // Round up to register pair alignment to avoid additional SP adjustment
+  // instructions.
+  AFI->setCalleeSavedStackSize(
+      alignTo(8 * (NumGPRSpilled + NumFPRSpilled), 16));
 }

test/CodeGen/AArch64/aarch64-dynamic-stack-layout.ll

entry:
   %add1 = add nsw i32 %add, %l1.0.l1.0.
   %call = tail call i32 @g()
   %add2 = add nsw i32 %add1, %call
   ret i32 %add2
 }
 ; CHECK-LABEL: novla_nodynamicrealign_call
 ; CHECK: .cfi_startproc
 ;   Check that used callee-saved registers are saved
-; CHECK: stp  x20, x19, [sp, #-32]!
+; CHECK: str  x19, [sp, #-32]!
 ;   Check that the frame pointer is created:
 ; CHECK: stp  x29, x30, [sp, #16]
 ; CHECK: add  x29, sp, #16
 ;   Check correctness of cfi pseudo-instructions
 ; CHECK: .cfi_def_cfa w29, 16
 ; CHECK: .cfi_offset w30, -8
 ; CHECK: .cfi_offset w29, -16
-; CHECK: .cfi_offset w19, -24
-; CHECK: .cfi_offset w20, -32
+; CHECK: .cfi_offset w19, -32
 ;   Check correct access to arguments passed on the stack, through frame pointer
 ; CHECK: ldr  d[[DARG:[0-9]+]], [x29, #40]
 ; CHECK: ldr  w[[IARG:[0-9]+]], [x29, #24]
 ;   Check correct access to local variable on the stack, through stack pointer
 ; CHECK: ldr  w[[ILOC:[0-9]+]], [sp, #12]
 ;   Check epilogue:
 ; CHECK: ldp  x29, x30, [sp, #16]
-; CHECK: ldp  x20, x19, [sp], #32
+; CHECK: ldr  x19, [sp], #32
 ; CHECK: ret
 ; CHECK: .cfi_endproc
 
 
 declare i32 @g() #0
 
 ; Function Attrs: nounwind
 define i32 @novla_nodynamicrealign_nocall(i32 %i1, i32 %i2, i32 %i3, i32 %i4, i32 %i5, i32 %i6, i32 %i7, i32 %i8, i32 %i9, i32 %i10, double %d1, double %d2, double %d3, double %d4, double %d5, double %d6, double %d7, double %d8, double %d9, double %d10) #1 {
entry:
   %call = tail call i32 @g()
   %add2 = add nsw i32 %add1, %call
   ret i32 %add2
 }
 
 ; CHECK-LABEL: novla_dynamicrealign_call
 ; CHECK: .cfi_startproc
 ;   Check that used callee-saved registers are saved
-; CHECK: stp  x20, x19, [sp, #-32]!
+; CHECK: str  x19, [sp, #-32]!
 ;   Check that the frame pointer is created:
 ; CHECK: stp  x29, x30, [sp, #16]
 ; CHECK: add  x29, sp, #16
 ;   Check the dynamic realignment of the stack pointer to a 128-byte boundary
 ; CHECK: sub  x9, sp, #96
 ; CHECK: and  sp, x9, #0xffffffffffffff80
 ;   Check correctness of cfi pseudo-instructions
 ; CHECK: .cfi_def_cfa w29, 16
 ; CHECK: .cfi_offset w30, -8
 ; CHECK: .cfi_offset w29, -16
-; CHECK: .cfi_offset w19, -24
-; CHECK: .cfi_offset w20, -32
+; CHECK: .cfi_offset w19, -32
 ;   Check correct access to arguments passed on the stack, through frame pointer
 ; CHECK: ldr  d[[DARG:[0-9]+]], [x29, #40]
 ; CHECK: ldr  w[[IARG:[0-9]+]], [x29, #24]
 ;   Check correct access to local variable on the stack, through re-aligned stack pointer
 ; CHECK: ldr  w[[ILOC:[0-9]+]], [sp]
 ;   Check epilogue:
 ;     Check that stack pointer get restored from frame pointer.
 ; CHECK: sub  sp, x29, #16            // =16
 ; CHECK: ldp  x29, x30, [sp, #16]
-; CHECK: ldp  x20, x19, [sp], #32
+; CHECK: ldr  x19, [sp], #32
 ; CHECK: ret
 ; CHECK: .cfi_endproc
 
 
 ; Function Attrs: nounwind
 define i32 @novla_dynamicrealign_nocall(i32 %i1, i32 %i2, i32 %i3, i32 %i4, i32 %i5, i32 %i6, i32 %i7, i32 %i8, i32 %i9, i32 %i10, double %d1, double %d2, double %d3, double %d4, double %d5, double %d6, double %d7, double %d8, double %d9, double %d10) #1 {
 entry:
   %l1 = alloca i32, align 128
entry:
   %1 = load volatile i32, i32* %vla, align 4, !tbaa !1
   %add3 = add nsw i32 %add2, %1
   ret i32 %add3
 }
 
 ; CHECK-LABEL: vla_dynamicrealign_call
 ; CHECK: .cfi_startproc
 ;   Check that used callee-saved registers are saved
-; CHECK: stp  x22, x21, [sp, #-48]!
+; CHECK: str  x21, [sp, #-48]!
 ; CHECK: stp  x20, x19, [sp, #16]
 ;   Check that the frame pointer is created:
 ; CHECK: stp  x29, x30, [sp, #32]
 ; CHECK: add  x29, sp, #32
 ;   Check that the stack pointer gets re-aligned to 128
 ;   bytes & the base pointer (x19) gets initialized to
 ;   this 128-byte aligned area for local variables &
 ;   spill slots
 ; CHECK: sub  x9, sp, #80            // =80
 ; CHECK: and  sp, x9, #0xffffffffffffff80
 ; CHECK: mov    x19, sp
 ;   Check correctness of cfi pseudo-instructions
 ; CHECK: .cfi_def_cfa w29, 16
 ; CHECK: .cfi_offset w30, -8
 ; CHECK: .cfi_offset w29, -16
 ; CHECK: .cfi_offset w19, -24
 ; CHECK: .cfi_offset w20, -32
-; CHECK: .cfi_offset w21, -40
-; CHECK: .cfi_offset w22, -48
+; CHECK: .cfi_offset w21, -48
 ;   Check correct access to arguments passed on the stack, through frame pointer
 ; CHECK: ldr  w[[IARG:[0-9]+]], [x29, #24]
 ; CHECK: ldr  d[[DARG:[0-9]+]], [x29, #40]
 ;   Check correct reservation of 16-byte aligned VLA (size in w0) on stack
 ;   and set-up of base pointer (x19).
 ; CHECK: mov  w9, w0
 ; CHECK: mov   x10, sp
 ; CHECK: lsl  x9, x9, #2
 ; CHECK: add  x9, x9, #15
 ; CHECK: and  x9, x9, #0x7fffffff0
 ; CHECK: sub   x[[VLASPTMP:[0-9]+]], x10, x9
 ; CHECK: mov   sp, x[[VLASPTMP]]
 ;   Check correct access to local variable, through base pointer
 ; CHECK: ldr  w[[ILOC:[0-9]+]], [x19]
 ; CHECK: ldr   w[[VLA:[0-9]+]], [x[[VLASPTMP]]]
 ;   Check epilogue:
 ;     Check that stack pointer get restored from frame pointer.
 ; CHECK: sub  sp, x29, #32
 ; CHECK: ldp  x29, x30, [sp, #32]
 ; CHECK: ldp  x20, x19, [sp, #16]
-; CHECK: ldp  x22, x21, [sp], #48
+; CHECK: ldr  x21, [sp], #48
 ; CHECK: ret
 ; CHECK: .cfi_endproc
 
 
 ; Function Attrs: nounwind
 define i32 @vla_dynamicrealign_nocall(i32 %i1, i32 %i2, i32 %i3, i32 %i4, i32 %i5, i32 %i6, i32 %i7, i32 %i8, i32 %i9, i32 %i10, double %d1, double %d2, double %d3, double %d4, double %d5, double %d6, double %d7, double %d8, double %d9, double %d10) #1 {
 entry:
   %l1 = alloca i32, align 128
   %0 = zext i32 %i1 to i64
   %vla = alloca i32, i64 %0, align 4
   %conv = fptosi double %d10 to i32
   %add = add nsw i32 %conv, %i10
   %l1.0.l1.0. = load volatile i32, i32* %l1, align 128
   %add1 = add nsw i32 %add, %l1.0.l1.0.
   %1 = load volatile i32, i32* %vla, align 4, !tbaa !1
   %add2 = add nsw i32 %add1, %1
   ret i32 %add2
 }
 
 ; CHECK-LABEL: vla_dynamicrealign_nocall
 ;   Check that used callee-saved registers are saved
-; CHECK: stp  x20, x19, [sp, #-32]!
+; CHECK: str  x19, [sp, #-32]!
 ;   Check that the frame pointer is created:
 ; CHECK: stp  x29, x30, [sp, #16]
 ; CHECK: add  x29, sp, #16
 ;   Check that the stack pointer gets re-aligned to 128
 ;   bytes & the base pointer (x19) gets initialized to
 ;   this 128-byte aligned area for local variables &
 ;   spill slots
 ; CHECK: sub  x9, sp, #96

 ; CHECK: mov   sp, x[[VLASPTMP]]
 ;   Check correct access to local variable, through base pointer
 ; CHECK: ldr  w[[ILOC:[0-9]+]], [x19]
 ; CHECK: ldr   w[[VLA:[0-9]+]], [x[[VLASPTMP]]]
 ;   Check epilogue:
 ;     Check that stack pointer get restored from frame pointer.
 ; CHECK: sub  sp, x29, #16
 ; CHECK: ldp  x29, x30, [sp, #16]
-; CHECK: ldp  x20, x19, [sp], #32
+; CHECK: ldr  x19, [sp], #32
 ; CHECK: ret
 
 
 ; Function Attrs: nounwind
 define i32 @vla_dynamicrealign_nocall_large_align(i32 %i1, i32 %i2, i32 %i3, i32 %i4, i32 %i5, i32 %i6, i32 %i7, i32 %i8, i32 %i9, i32 %i10, double %d1, double %d2, double %d3, double %d4, double %d5, double %d6, double %d7, double %d8, double %d9, double %d10) #1 {
 entry:
   %l1 = alloca i32, align 32768
   %0 = zext i32 %i1 to i64
   %vla = alloca i32, i64 %0, align 4
   %conv = fptosi double %d10 to i32
   %add = add nsw i32 %conv, %i10
   %l1.0.l1.0. = load volatile i32, i32* %l1, align 32768
   %add1 = add nsw i32 %add, %l1.0.l1.0.
   %1 = load volatile i32, i32* %vla, align 4, !tbaa !1
   %add2 = add nsw i32 %add1, %1
   ret i32 %add2
 }
 
 ; CHECK-LABEL: vla_dynamicrealign_nocall_large_align
 ;   Check that used callee-saved registers are saved
-; CHECK: stp  x20, x19, [sp, #-32]!
+; CHECK: stp  x28, x19, [sp, #-32]!
 ;   Check that the frame pointer is created:
 ; CHECK: stp  x29, x30, [sp, #16]
 ; CHECK: add  x29, sp, #16
 ;   Check that the stack pointer gets re-aligned to 128
 ;   bytes & the base pointer (x19) gets initialized to
 ;   this 128-byte aligned area for local variables &
 ;   spill slots
 ; CHECK: sub  x9, sp, #7, lsl #12

 ; CHECK: mov   sp, x[[VLASPTMP]]
 ;   Check correct access to local variable, through base pointer
 ; CHECK: ldr  w[[ILOC:[0-9]+]], [x19]
 ; CHECK: ldr   w[[VLA:[0-9]+]], [x[[VLASPTMP]]]
 ;   Check epilogue:
 ;     Check that stack pointer get restored from frame pointer.
 ; CHECK: sub  sp, x29, #16
 ; CHECK: ldp  x29, x30, [sp, #16]
-; CHECK: ldp  x20, x19, [sp], #32
+; CHECK: ldp  x28, x19, [sp], #32
 ; CHECK: ret
 
 
 define void @realign_conditional(i1 %b) {
 entry:
   br i1 %b, label %bb0, label %bb1
 
 bb0:

test/CodeGen/AArch64/alloca.ll

 ; CHECK-NOFP-ARM64: mov sp, x29
 ; CHECK-NOFP-ARM64: ldp x29, x30, [sp], #16
 }
 
 define void @test_alloca_large_frame(i64 %n) {
 ; CHECK-LABEL: test_alloca_large_frame:
 
 
-; CHECK: stp     x20, x19, [sp, #-32]!
+; CHECK: stp     x28, x19, [sp, #-32]!
 ; CHECK: stp     x29, x30, [sp, #16]
 ; CHECK: add     x29, sp, #16
 ; CHECK: sub     sp, sp, #1953, lsl #12
 ; CHECK: sub     sp, sp, #512
 
   %addr1 = alloca i8, i64 %n
   %addr2 = alloca i64, i64 1000000
 
   call void @use_addr_loc(i8* %addr1, i64* %addr2)
 
   ret void
 
 ; CHECK: sub     sp, x29, #16
 ; CHECK: ldp     x29, x30, [sp, #16]
-; CHECK: ldp     x20, x19, [sp], #32
+; CHECK: ldp     x28, x19, [sp], #32
 }
 
 declare i8* @llvm.stacksave()
 declare void @llvm.stackrestore(i8*)
 
 define void @test_scoped_alloca(i64 %n) {
 ; CHECK-LABEL: test_scoped_alloca:
 

test/CodeGen/AArch64/arm64-frame-index.ll

 ; RUN: llc -march=arm64 -mtriple=arm64-apple-ios -aarch64-atomic-cfg-tidy=0 < %s | FileCheck %s
 ; rdar://11935841
 
 define void @t1() nounwind ssp {
 entry:
 ; CHECK-LABEL: t1:
 ; CHECK-NOT: add x{{[0-9]+}}, sp
-; CHECK: stp x28, x27, [sp, #-16]!
+; CHECK: str x28, [sp, #-16]!
   %v = alloca [288 x i32], align 4
   unreachable
 }

test/CodeGen/AArch64/arm64-inline-asm.ll

 }
 
 ; rdar://10258229
 ; ARM64TargetLowering::getRegForInlineAsmConstraint() should recognize 'v'
 ; registers.
 define void @t8() nounwind ssp {
 entry:
 ; CHECK-LABEL: t8:
-; CHECK: stp {{d[0-9]+}}, {{d[0-9]+}}, [sp, #-16]
+; CHECK: str d8, [sp, #-16]
   tail call void asm sideeffect "nop", "~{v8}"() nounwind
   ret void
 }
 
 define i32 @constraint_I(i32 %i, i32 %j) nounwind {
 entry:
   ; CHECK-LABEL: constraint_I:
   %0 = tail call i32 asm sideeffect "add ${0:w}, ${1:w}, $2", "=r,r,I"(i32 %i, i32 16773120) nounwind

test/CodeGen/AArch64/arm64-register-pairing.ll

 ; RUN: llc -mtriple=arm64-apple-ios < %s | FileCheck %s
 ;
 ; rdar://14075006
 
 define void @odd() nounwind {
 ; CHECK-LABEL: odd:
-; CHECK: stp d15, d14, [sp, #-144]!
-; CHECK: stp d13, d12, [sp, #16]
-; CHECK: stp d11, d10, [sp, #32]
-; CHECK: stp d9, d8, [sp, #48]
-; CHECK: stp x28, x27, [sp, #64]
-; CHECK: stp x26, x25, [sp, #80]
-; CHECK: stp x24, x23, [sp, #96]
-; CHECK: stp x22, x21, [sp, #112]
-; CHECK: stp x20, x19, [sp, #128]
+; CHECK: stp d14, d12, [sp, #-80]!
+; CHECK: stp d10, d8, [sp, #16]
+; CHECK: str x27, [sp, #32]
+; CHECK: stp x25, x23, [sp, #48]
+; CHECK: stp x21, x19, [sp, #64]
 ; CHECK: movz x0, #0x2a
-; CHECK: ldp x20, x19, [sp, #128]
-; CHECK: ldp x22, x21, [sp, #112]
-; CHECK: ldp x24, x23, [sp, #96]
-; CHECK: ldp x26, x25, [sp, #80]
-; CHECK: ldp x28, x27, [sp, #64]
-; CHECK: ldp d9, d8, [sp, #48]
-; CHECK: ldp d11, d10, [sp, #32]
-; CHECK: ldp d13, d12, [sp, #16]
-; CHECK: ldp d15, d14, [sp], #144
+; CHECK: ldp x21, x19, [sp, #64]
+; CHECK: ldp x25, x23, [sp, #48]
+; CHECK: ldr x27, [sp, #32]
+; CHECK: ldp d10, d8, [sp, #16]
+; CHECK: ldp d14, d12, [sp], #80
   call void asm sideeffect "mov x0, #42", "~{x0},~{x19},~{x21},~{x23},~{x25},~{x27},~{d8},~{d10},~{d12},~{d14}"() nounwind
   ret void
 }
 
 define void @even() nounwind {
 ; CHECK-LABEL: even:
-; CHECK: stp d15, d14, [sp, #-144]!
-; CHECK: stp d13, d12, [sp, #16]
-; CHECK: stp d11, d10, [sp, #32]
-; CHECK: stp d9, d8, [sp, #48]
-; CHECK: stp x28, x27, [sp, #64]
-; CHECK: stp x26, x25, [sp, #80]
-; CHECK: stp x24, x23, [sp, #96]
-; CHECK: stp x22, x21, [sp, #112]
-; CHECK: stp x20, x19, [sp, #128]
+; CHECK: stp d15, d13, [sp, #-80]!
+; CHECK: stp d11, d9, [sp, #16]
+; CHECK: str x28, [sp, #32]
+; CHECK: stp x26, x24, [sp, #48]
+; CHECK: stp x22, x20, [sp, #64]
 ; CHECK: movz x0, #0x2a
-; CHECK: ldp x20, x19, [sp, #128]
-; CHECK: ldp x22, x21, [sp, #112]
-; CHECK: ldp x24, x23, [sp, #96]
-; CHECK: ldp x26, x25, [sp, #80]
-; CHECK: ldp x28, x27, [sp, #64]
-; CHECK: ldp d9, d8, [sp, #48]
-; CHECK: ldp d11, d10, [sp, #32]
-; CHECK: ldp d13, d12, [sp, #16]
-; CHECK: ldp d15, d14, [sp], #144
+; CHECK: ldp x22, x20, [sp, #64]
+; CHECK: ldp x26, x24, [sp, #48]
+; CHECK: ldr x28, [sp, #32]
+; CHECK: ldp d11, d9, [sp, #16]
+; CHECK: ldp d15, d13, [sp], #80
   call void asm sideeffect "mov x0, #42", "~{x0},~{x20},~{x22},~{x24},~{x26},~{x28},~{d9},~{d11},~{d13},~{d15}"() nounwind
   ret void
 }

test/CodeGen/AArch64/arm64-shrink-wrapping.ll

 
 ; Check that we handle inline asm correctly.
 ; CHECK-LABEL: inlineAsm:
 ;
 ; ENABLE: cbz w0, [[ELSE_LABEL:LBB[0-9_]+]]
 ;
 ; Prologue code.
 ; Make sure we save the CSR used in the inline asm: x19.
-; CHECK: stp [[CSR1:x[0-9]+]], [[CSR2:x19]], [sp, #-16]!
+; CHECK: str [[CSR:x19]], [sp, #-16]!
 ;
 ; DISABLE: cbz w0, [[ELSE_LABEL:LBB[0-9_]+]]
 ;
 ; CHECK: movz [[IV:w[0-9]+]], #0xa
 ;
 ; CHECK: [[LOOP_LABEL:LBB[0-9_]+]]: ; %for.body
 ; Inline asm statement.
 ; CHECK: add x19, x19, #1
 ; CHECK: sub [[IV]], [[IV]], #1
 ; CHECK-NEXT: cbnz [[IV]], [[LOOP_LABEL]]
 ; Next BB.
 ; CHECK: mov w0, wzr
 ; Epilogue code.
-; CHECK-NEXT: ldp [[CSR1]], [[CSR2]], [sp], #16
+; CHECK-NEXT: ldr [[CSR]], [sp], #16
 ; CHECK-NEXT: ret
 ; Next BB.
 ; CHECK: [[ELSE_LABEL]]: ; %if.else
 ; CHECK-NEXT: lsl w0, w1, #1
 ; Epilogue code.
-; DISABLE-NEXT: ldp [[CSR1]], [[CSR2]], [sp], #16
+; DISABLE-NEXT: ldr [[CSR]], [sp], #16
 ; CHECK-NEXT: ret
 define i32 @inlineAsm(i32 %cond, i32 %N) {
 entry:
   %tobool = icmp eq i32 %cond, 0
   br i1 %tobool, label %if.else, label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.03 = phi i32 [ %inc, %for.body ], [ 0, %entry ]