ARMLoadStoreOptimizer: Create LDRD/STRD on thumb2

[MatzeB]

Summary

This patch extends the Post-RA LoadStoreOptimizer to form STRD/LDRD instructions on thumb2. While the Pre-RA LDRD/STRD formation already catches many cases we can now also catch spills and reloads.

This builds upon http://reviews.llvm.org/D10140.

[rengolin]

With a few nitpicks, looks good to me. John, any comments?

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

756

nitpick: I'd have kept isi32Load(Opecode) in a bool IsLoad, and reused it on all cases.

933

nitpick: variable name too close to CanMergeToLoadStoreMulti, confusing.

946

this is a bit confusing... probably because of the close variable names, but also because of the chain of conditionals. Maybe it'll get better after you renamed the *This* variants to something smaller and more distinct.

1744

better to leave if (! ...) here, not an empty block.

[john.brawn]

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

933–949

I think the logic here could be made much clearer by splitting it up something like

// Must access sequential ascending memory addresses
if (NewOffset != Offset + (int)Size)
  continue;
// Cannot load SP
if (Reg == ARM::SP)
  continue;
// VFP must load contiguous ascending registers, non-VFP must load ascending registers
CanMergeThisToLoadStoreMulti = (isNotVFP ? RegNum <= PRegNum : (Count < Limit) && RegNum == PRegNum+1))

The swift check I think can be done outside the loop, as it depends only on the first register. Instead of having CanMergeThisToLoadStoreDouble maybe just later set Candidate->CanMergeToLoadStoreDouble = CanMergeToLoadStoreDouble && Count == 2.

936

Only LDRD and not STRD, so should have || !isi32Load(Opcode)

[MatzeB]

Thanks for the reviews!

I put some of the cleanups suggested for FormCandidates() into the cleanup patch at http://reviews.llvm.org/D10140. The rest should be addressed in this new version.

[rengolin]

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

761

you could also use IsLoad here, too.

[MatzeB]

Implement review suggestion.

[rengolin]

LGTM now. Thanks!

[MatzeB]

Thanks for the review. I can't commit this yet until http://reviews.llvm.org/D10140 is approved.

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

struct MergeCandidate {
       SmallVector<MachineInstr*, 4> Instrs;
       /// Index in Instrs of the instruction being latest in the schedule.
       unsigned LatestMIIdx;
       /// Index in Instrs of the instruction being earliest in the schedule.
       unsigned EarliestMIIdx;
       /// Index into the basic block where the merged instruction will be
       /// inserted. (See MemOpQueueEntry.Position)
       unsigned InsertPos;
+      /// Whether the instructions can be merged into a ldm/stm instruction.
+      bool CanMergeToLSMulti;
+      /// Whether the instructions can be merged into a ldrd/strd instruction.
+      bool CanMergeToLSDouble;
     };
     BumpPtrAllocator Allocator;
     SmallVector<const MergeCandidate*,4> Candidates;
 
     void moveLiveRegsBefore(const MachineBasicBlock &MBB,
                             MachineBasicBlock::const_iterator Before);
     unsigned findFreeReg(const TargetRegisterClass &RegClass);
     void UpdateBaseRegUses(MachineBasicBlock &MBB,
                            MachineBasicBlock::iterator MBBI,
                            DebugLoc DL, unsigned Base, unsigned WordOffset,
                            ARMCC::CondCodes Pred, unsigned PredReg);
-    MachineInstr *MergeOps(MachineBasicBlock &MBB,
-                           MachineBasicBlock::iterator InsertBefore, int Offset,
-                           unsigned Base, bool BaseKill, unsigned Opcode,
-                           ARMCC::CondCodes Pred, unsigned PredReg, DebugLoc DL,
-                           ArrayRef<std::pair<unsigned, bool>> Regs);
+    MachineInstr *CreateLoadStoreMulti(MachineBasicBlock &MBB,
+        MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
+        bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
+        DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs);
+    MachineInstr *CreateLoadStoreDouble(MachineBasicBlock &MBB,
+        MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
+        bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
+        DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs) const;
     void FormCandidates(const MemOpQueue &MemOps);
     MachineInstr *MergeOpsUpdate(const MergeCandidate &Cand);
     bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
                              MachineBasicBlock::iterator &MBBI);
     bool MergeBaseUpdateLoadStore(MachineInstr *MI);
     bool MergeBaseUpdateLSMultiple(MachineInstr *MI);
     bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
     bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
for (const std::pair<unsigned, bool> &R : Regs)
     if (R.first == Reg)
       return true;
   return false;
 }
 
 /// Create and insert a LDM or STM with Base as base register and registers in
 /// Regs as the register operands that would be loaded / stored.  It returns
 /// true if the transformation is done.
-MachineInstr *
-ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB,
-                          MachineBasicBlock::iterator InsertBefore, int Offset,
-                          unsigned Base, bool BaseKill, unsigned Opcode,
-                          ARMCC::CondCodes Pred, unsigned PredReg, DebugLoc DL,
-                          ArrayRef<std::pair<unsigned, bool>> Regs) {
+MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(MachineBasicBlock &MBB,
+    MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
+    bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
+    DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs) {
   unsigned NumRegs = Regs.size();
   assert(NumRegs > 1);
 
   // For Thumb1 targets, it might be necessary to clobber the CPSR to merge.
   // Compute liveness information for that register to make the decision.
   bool SafeToClobberCPSR = !isThumb1 ||
     (MBB.computeRegisterLiveness(TRI, ARM::CPSR, InsertBefore, 20) ==
      MachineBasicBlock::LQR_Dead);
MachineInstr *ARMLoadStoreOpt::CreateLoadStoreMulti(MachineBasicBlock &MBB,
   MIB.addImm(Pred).addReg(PredReg);
 
   for (const std::pair<unsigned, bool> &R : Regs)
     MIB.addReg(R.first, getDefRegState(isDef) | getKillRegState(R.second));
 
   return MIB.getInstr();
 }
 
+MachineInstr *ARMLoadStoreOpt::CreateLoadStoreDouble(MachineBasicBlock &MBB,
+    MachineBasicBlock::iterator InsertBefore, int Offset, unsigned Base,
+    bool BaseKill, unsigned Opcode, ARMCC::CondCodes Pred, unsigned PredReg,
+    DebugLoc DL, ArrayRef<std::pair<unsigned, bool>> Regs) const {
+  bool IsLoad = isi32Load(Opcode);
+  assert((IsLoad || isi32Store(Opcode)) && "Must have integer load or store");
+  unsigned LoadStoreOpcode = IsLoad ? ARM::t2LDRDi8 : ARM::t2STRDi8;
+
+  assert(Regs.size() == 2);
+  MachineInstrBuilder MIB = BuildMI(MBB, InsertBefore, DL,
+                                    TII->get(LoadStoreOpcode));
+  if (LoadStoreOpcode == ARM::t2LDRDi8) {
+    MIB.addReg(Regs[0].first, RegState::Define)
+       .addReg(Regs[1].first, RegState::Define);
+  } else {
+    MIB.addReg(Regs[0].first, getKillRegState(Regs[0].second))
+       .addReg(Regs[1].first, getKillRegState(Regs[1].second));
+  }
+  MIB.addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
+  return MIB.getInstr();
+}
+
 /// Call MergeOps and update MemOps and merges accordingly on success.
 MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
   const MachineInstr *First = Cand.Instrs.front();
   unsigned Opcode = First->getOpcode();
   bool IsLoad = isLoad(Opcode);
   SmallVector<std::pair<unsigned, bool>, 8> Regs;
   SmallVector<unsigned, 4> ImpDefs;
   DenseSet<unsigned> KilledRegs;
MachineInstr *ARMLoadStoreOpt::MergeOpsUpdate(const MergeCandidate &Cand) {
   iterator InsertBefore = std::next(iterator(LatestMI));
   MachineBasicBlock &MBB = *LatestMI->getParent();
   unsigned Offset = getMemoryOpOffset(First);
   unsigned Base = getLoadStoreBaseOp(*First).getReg();
   bool BaseKill = LatestMI->killsRegister(Base);
   unsigned PredReg = 0;
   ARMCC::CondCodes Pred = getInstrPredicate(First, PredReg);
   DebugLoc DL = First->getDebugLoc();
-  MachineInstr *Merged = MergeOps(MBB, InsertBefore, Offset, Base, BaseKill,
+  MachineInstr *Merged = nullptr;
+  if (Cand.CanMergeToLSDouble)
+    Merged = CreateLoadStoreDouble(MBB, InsertBefore, Offset, Base, BaseKill,
+                                   Opcode, Pred, PredReg, DL, Regs);
+  if (!Merged && Cand.CanMergeToLSMulti)
+    Merged = CreateLoadStoreMulti(MBB, InsertBefore, Offset, Base, BaseKill,
                                   Opcode, Pred, PredReg, DL, Regs);
   if (!Merged)
     return nullptr;
 
   // Determine earliest instruction that will get removed. We then keep an
   // iterator just above it so the following erases don't invalidated it.
   iterator EarliestI(Cand.Instrs[Cand.EarliestMIIdx]);
   bool EarliestAtBegin = false;
for (MachineInstr &MI : FixupRange) {
       }
     }
     assert(ImpDefs.empty());
   }
 
   return Merged;
 }
 
+static bool isValidLSDoubleOffset(int Offset) {
+  unsigned Value = abs(Offset);
+  // t2LDRDi8/t2STRDi8 supports an 8 bit immediate which is internally
+  // multiplied by 4.
+  return (Value % 4) == 0 && Value < 1024;
+}
+
 /// Find candidates for load/store multiple merge in list of MemOpQueueEntries.
 void ARMLoadStoreOpt::FormCandidates(const MemOpQueue &MemOps) {
   const MachineInstr *FirstMI = MemOps[0].MI;
   unsigned Opcode = FirstMI->getOpcode();
   bool isNotVFP = isi32Load(Opcode) || isi32Store(Opcode);
   unsigned Size = getLSMultipleTransferSize(FirstMI);
   // vldm / vstm limit are 32 for S variants, 16 for D variants.
   unsigned Limit;
do {
     const MachineInstr *MI = MemOps[SIndex].MI;
     int Offset = MemOps[SIndex].Offset;
     const MachineOperand &PMO = getLoadStoreRegOp(*MI);
     unsigned PReg = PMO.getReg();
     unsigned PRegNum = PMO.isUndef() ? UINT_MAX : TRI->getEncodingValue(PReg);
     unsigned Latest = SIndex;
     unsigned Earliest = SIndex;
     unsigned Count = 1;
+    bool CanMergeToLSDouble =
+      STI->isThumb2() && isNotVFP && isValidLSDoubleOffset(Offset);
+    // ARM errata 602117: LDRD with base in list may result in incorrect base
+    // register when interrupted or faulted.
+    if (STI->isCortexM3() && isi32Load(Opcode) &&
+        PReg == getLoadStoreBaseOp(*MI).getReg())
+      CanMergeToLSDouble = false;
+
+    bool CanMergeToLSMulti = true;
+    // On swift vldm/vstm starting with an odd register number as that needs
+    // more uops than single vldrs.
+    if (STI->isSwift() && !isNotVFP && (PRegNum % 2) == 1)
+      CanMergeToLSMulti = false;
 
-    // Merge additional instructions fulfilling LDM/STM constraints.
+    // Merge following instructions where possible.
     for (unsigned I = SIndex+1; I < EIndex; ++I, ++Count) {
       int NewOffset = MemOps[I].Offset;
       if (NewOffset != Offset + (int)Size)
         break;
       const MachineOperand &MO = getLoadStoreRegOp(*MemOps[I].MI);
       unsigned Reg = MO.getReg();
-      if (Reg == ARM::SP)
-        break;
       unsigned RegNum = MO.isUndef() ? UINT_MAX : TRI->getEncodingValue(Reg);
+
+      // See if the current load/store may be part of a multi load/store.
+      bool PartOfLSMulti = CanMergeToLSMulti;
+      if (PartOfLSMulti) {
+        // Cannot load from SP
+        if (Reg == ARM::SP)
+          PartOfLSMulti = false;
         // Register numbers must be in ascending order.
-      if (RegNum <= PRegNum)
-        break;
-      // For VFP / NEON load/store multiples, the registers must be consecutive
-      // and within the limit on the number of registers per instruction.
-      if (!isNotVFP && RegNum != PRegNum+1)
-        break;
-      // On Swift we don't want vldm/vstm to start with a odd register num
-      // because Q register unaligned vldm/vstm need more uops.
-      if (!isNotVFP && STI->isSwift() && Count == 1 && (PRegNum % 2) == 1)
-        break;
+        else if (RegNum <= PRegNum)
+          PartOfLSMulti = false;
+        // For VFP / NEON load/store multiples, the registers must be
+        // consecutive and within the limit on the number of registers per
+        // instruction.
+        else if (!isNotVFP && RegNum != PRegNum+1)
+          PartOfLSMulti = false;
+      }
+      // See if the current load/store may be part of a double load/store.
+      bool PartOfLSDouble = CanMergeToLSDouble && Count <= 1;
 
+      if (!PartOfLSMulti && !PartOfLSDouble)
+        break;
+      CanMergeToLSMulti &= PartOfLSMulti;
+      CanMergeToLSDouble &= PartOfLSDouble;
       // Track MemOp with latest and earliest position (Positions are
       // counted in reverse).
       unsigned Position = MemOps[I].Position;
       if (Position < MemOps[Latest].Position)
         Latest = I;
       else if (Position > MemOps[Earliest].Position)
         Earliest = I;
       // Prepare for next MemOp.
       Offset += Size;
       PRegNum = RegNum;
     }
 
     // Form a candidate from the Ops collected so far.
     MergeCandidate *Candidate = new(Allocator) MergeCandidate;
     for (unsigned C = SIndex, CE = SIndex + Count; C < CE; ++C)
       Candidate->Instrs.push_back(MemOps[C].MI);
     Candidate->LatestMIIdx = Latest - SIndex;
     Candidate->EarliestMIIdx = Earliest - SIndex;
     Candidate->InsertPos = MemOps[Latest].Position;
+    if (Count == 1)
+      CanMergeToLSMulti = CanMergeToLSDouble = false;
+    Candidate->CanMergeToLSMulti = CanMergeToLSMulti;
+    Candidate->CanMergeToLSDouble = CanMergeToLSDouble;
     Candidates.push_back(Candidate);
     // Continue after the chain.
     SIndex += Count;
   } while (SIndex < EIndex);
 }
 
 static bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
                                 unsigned Bytes, unsigned Limit,
bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) {
   auto LessThan = [](const MergeCandidate* M0, const MergeCandidate *M1) {
     return M0->InsertPos < M1->InsertPos;
   };
   std::sort(Candidates.begin(), Candidates.end(), LessThan);
 
   // Go through list of candidates and merge.
   bool Changed = false;
   for (const MergeCandidate *Candidate : Candidates) {
-    if (Candidate->Instrs.size() > 1) {
+    if (Candidate->CanMergeToLSMulti || Candidate->CanMergeToLSDouble) {
       MachineInstr *Merged = MergeOpsUpdate(*Candidate);
       // Merge preceding/trailing base inc/dec into the merged op.
       if (Merged) {
-        MergeBaseUpdateLSMultiple(Merged);
         Changed = true;
+        unsigned Opcode = Merged->getOpcode();
+        if (Opcode != ARM::t2STRDi8 && Opcode != ARM::t2LDRDi8)
+          MergeBaseUpdateLSMultiple(Merged);
       } else {
         for (MachineInstr *MI : Candidate->Instrs) {
           if (MergeBaseUpdateLoadStore(MI))
             Changed = true;
         }
       }
     } else {
       assert(Candidate->Instrs.size() == 1);

test/CodeGen/ARM/2013-05-02-AAPCS-ByVal-Structs-C4-C5-VFP.ll

define void @foo(double %vfp0,     ; --> D0,     NSAA=SP
      %st_t* byval %p1, ; --> R1, R2, NSAA=SP+8
      i32 %p2,          ; --> R3,     NSAA=SP+8 
                  i32 %p3) #0 {     ; --> SP+4,   NSAA=SP+12
 entry:
   ;CHECK: sub sp, #12
   ;CHECK: push {r7, lr}
   ;CHECK: sub sp, #4
   ;CHECK: add r0, sp, #12
-  ;CHECK: str r2, [sp, #16]
-  ;CHECK: str r1, [sp, #12]
+  ;CHECK: strd r1, r2, [sp, #12]
   ;CHECK: bl  fooUseStruct
   call void @fooUseStruct(%st_t* %p1)
   ret void
 }
 
 define void @doFoo() {
 entry:
   call void @foo(double 23.0,

test/CodeGen/ARM/byval-align.ll

 ; byval align 8 can, but we used to incorrectly set r7 here (miscalculating the
 ; space taken up by arg regs).
 define i32 @test_align8(i8*, [4 x i32]* byval align 8 %b) {
 ; CHECK-LABEL: test_align8:
 ; CHECK: sub sp, #8
 ; CHECK: push {r4, r7, lr}
 ; CHECK: add r7, sp, #4
 
-; CHECK-DAG: str r2, [r7, #8]
-; CHECK-DAG: str r3, [r7, #12]
+; CHECK: strd r2, r3, [r7, #8]
 
 ; CHECK: ldr r0, [r7, #8]
 
   call void @bar()
   %valptr = getelementptr [4 x i32], [4 x i32]* %b, i32 0, i32 0
   %val = load i32, i32* %valptr
   ret i32 %val
 }

test/CodeGen/ARM/ldrd.ll

 ; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-a8 -regalloc=fast -optimize-regalloc=0 | FileCheck %s -check-prefix=A8 -check-prefix=CHECK
 ; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-m3 -regalloc=fast -optimize-regalloc=0 | FileCheck %s -check-prefix=M3 -check-prefix=CHECK
 ; rdar://6949835
 ; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-a8 -regalloc=basic | FileCheck %s -check-prefix=BASIC -check-prefix=CHECK
 ; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-a8 -regalloc=greedy | FileCheck %s -check-prefix=GREEDY -check-prefix=CHECK
+; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=swift | FileCheck %s -check-prefix=SWIFT -check-prefix=CHECK
 
 ; Magic ARM pair hints works best with linearscan / fast.
 
 @b = external global i64*
 
 ; We use the following two to force values into specific registers.
 declare i64* @get_ptr()
 declare void @use_i64(i64 %v)
entry:
   %addr1 = getelementptr i32, i32* %p, i32 1
   %v0 = load i32, i32* %addr0
   %v1 = load i32, i32* %addr1
   ; try to force %v0/%v1 into non-adjacent registers
   call void @extfunc(i32 %v0, i32 0, i32 0, i32 %v1)
   ret void
 }
 
+; CHECK-LABEL: strd_spill_ldrd_reload:
+; A8: strd r1, r0, [sp]
+; M3: strd r1, r0, [sp]
+; BASIC: strd r1, r0, [sp]
+; GREEDY: strd r0, r1, [sp]
+; CHECK: @ InlineAsm Start
+; CHECK: @ InlineAsm End
+; A8: ldrd r2, r1, [sp]
+; M3: ldrd r2, r1, [sp]
+; BASIC: ldrd r2, r1, [sp]
+; GREEDY: ldrd r1, r2, [sp]
+; CHECK: bl{{x?}} _extfunc
+define void @strd_spill_ldrd_reload(i32 %v0, i32 %v1) {
+  ; force %v0 and %v1 to be spilled
+  call void asm sideeffect "", "~{r0},~{r1},~{r2},~{r3},~{r4},~{r5},~{r6},~{r7},~{r8},~{r9},~{r10},~{r11},~{r12},~{lr}"()
+  ; force the reloaded %v0, %v1 into different registers
+  call void @extfunc(i32 0, i32 %v0, i32 %v1, i32 7)
+  ret void
+}
+
 declare void @llvm.lifetime.start(i64, i8* nocapture) nounwind
 declare void @llvm.lifetime.end(i64, i8* nocapture) nounwind

test/CodeGen/ARM/memset-inline.ll

 ; RUN: llc < %s -mtriple=thumbv7-apple-ios -mcpu=cortex-a8 -pre-RA-sched=source -disable-post-ra | FileCheck %s
 
 define void @t1(i8* nocapture %c) nounwind optsize {
 entry:
 ; CHECK-LABEL: t1:
 ; CHECK: movs r1, #0
-; CHECK: str r1, [r0]
-; CHECK: str r1, [r0, #4]
+; CHECK: strd r1, r1, [r0]
 ; CHECK: str r1, [r0, #8]
   call void @llvm.memset.p0i8.i64(i8* %c, i8 0, i64 12, i32 8, i1 false)
   ret void
 }
 
 define void @t2() nounwind ssp {
 entry:
 ; CHECK-LABEL: t2:

test/CodeGen/Thumb2/aapcs.ll

 ; SOFT: ldr r0, [sp, #48]
 ; HARD: vldr s0, [sp]
 ; CHECK-NEXT: bx lr
   ret float %i
 }
 
 define double @double_on_stack(double %a, double %b, double %c, double %d, double %e, double %f, double %g, double %h, double %i) {
 ; CHECK-LABEL: double_on_stack:
-; SOFT: ldr r0, [sp, #48]
-; SOFT: ldr r1, [sp, #52]
+; SOFT: ldrd r0, r1, [sp, #48]
 ; HARD: vldr d0, [sp]
 ; CHECK-NEXT: bx lr
   ret double %i
 }
 
 define double @double_not_split(double %a, double %b, double %c, double %d, double %e, double %f, double %g, float %h, double %i) {
 ; CHECK-LABEL: double_not_split:
-; SOFT: ldr r0, [sp, #48]
-; SOFT: ldr r1, [sp, #52]
+; SOFT: ldrd r0, r1, [sp, #48]
 ; HARD: vldr d0, [sp]
 ; CHECK-NEXT: bx lr
   ret double %i
 }