[ARM] Use alias analysis in ARMPreAllocLoadStoreOpt.

[efriedma]

Summary

This allows the optimization to rearrange loads and stores more aggressively. This doesn't really affect performance, but it helps codesize.

[mcrosier]

LGTM. Also, I believe this addresses, at least in part, PR24418.

[mcrosier]

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

35

Is this include needed?

[mcrosier]

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

2028–2029

I believe this FIXME can be removed as well.

[mcrosier]

test/CodeGen/ARM/ldrd.ll

199

Sorry to come back around on this one, Eli. Would you mind writing this as a MIR test as is done in D30903? Otherwise, instruction scheduling or register allocation may affect this test.

[mcrosier]

test/CodeGen/ARM/ldrd.ll

199

Ignore the part about RA since this is pre-RA.

[efriedma]

Add MIR test. Minor cleanups.

[mcrosier]

LGTM. Thanks for addressing my comments and adding the MIR test case.

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/RegisterClassInfo.h"
 #include "llvm/CodeGen/SelectionDAGNodes.h"
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"

 
 namespace {
   /// Pre- register allocation pass that move load / stores from consecutive
   /// locations close to make it more likely they will be combined later.
   struct ARMPreAllocLoadStoreOpt : public MachineFunctionPass{
     static char ID;
     ARMPreAllocLoadStoreOpt() : MachineFunctionPass(ID) {}
 
+    AliasAnalysis *AA;
     const DataLayout *TD;
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     const ARMSubtarget *STI;
     MachineRegisterInfo *MRI;
     MachineFunction *MF;
 
     bool runOnMachineFunction(MachineFunction &Fn) override;
 
     StringRef getPassName() const override {
       return ARM_PREALLOC_LOAD_STORE_OPT_NAME;
     }
 
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<AAResultsWrapperPass>();
+      MachineFunctionPass::getAnalysisUsage(AU);
+    }
+
   private:
     bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl,
                           unsigned &NewOpc, unsigned &EvenReg,
                           unsigned &OddReg, unsigned &BaseReg,
                           int &Offset,
                           unsigned &PredReg, ARMCC::CondCodes &Pred,
                           bool &isT2);
     bool RescheduleOps(MachineBasicBlock *MBB,
if (AssumeMisalignedLoadStores || skipFunction(*Fn.getFunction()))
     return false;
 
   TD = &Fn.getDataLayout();
   STI = &static_cast<const ARMSubtarget &>(Fn.getSubtarget());
   TII = STI->getInstrInfo();
   TRI = STI->getRegisterInfo();
   MRI = &Fn.getRegInfo();
   MF  = &Fn;
+  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   bool Modified = false;
   for (MachineBasicBlock &MFI : Fn)
     Modified |= RescheduleLoadStoreInstrs(&MFI);
 
   return Modified;
 }
 
 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base,
                                       MachineBasicBlock::iterator I,
                                       MachineBasicBlock::iterator E,
                                       SmallPtrSetImpl<MachineInstr*> &MemOps,
                                       SmallSet<unsigned, 4> &MemRegs,
-                                      const TargetRegisterInfo *TRI) {
+                                      const TargetRegisterInfo *TRI,
+                                      AliasAnalysis *AA) {
   // Are there stores / loads / calls between them?
-  // FIXME: This is overly conservative. We should make use of alias information
-  // some day.
   SmallSet<unsigned, 4> AddedRegPressure;
   while (++I != E) {
     if (I->isDebugValue() || MemOps.count(&*I))
       continue;
     if (I->isCall() || I->isTerminator() || I->hasUnmodeledSideEffects())
       return false;
-    if (isLd && I->mayStore())
-      return false;
-    if (!isLd) {
-      if (I->mayLoad())
+    if (I->mayStore() || (!isLd && I->mayLoad()))
+      for (MachineInstr *MemOp : MemOps)
+        if (I->mayAlias(AA, *MemOp, /*UseTBAA*/ false))
           return false;
-      // It's not safe to move the first 'str' down.
-      // str r1, [r0]
-      // strh r5, [r0]
-      // str r4, [r0, #+4]
-      if (I->mayStore())
-        return false;
-    }
     for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) {
       MachineOperand &MO = I->getOperand(j);
       if (!MO.isReg())
         continue;
       unsigned Reg = MO.getReg();
       if (MO.isDef() && TRI->regsOverlap(Reg, Base))
         return false;
       if (Reg != Base && !MemRegs.count(Reg))
else {
         MemRegs.insert(Ops[i]->getOperand(0).getReg());
       }
 
       // Be conservative, if the instructions are too far apart, don't
       // move them. We want to limit the increase of register pressure.
       bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this.
       if (DoMove)
         DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp,
-                                           MemOps, MemRegs, TRI);
+                                           MemOps, MemRegs, TRI, AA);
       if (!DoMove) {
         for (unsigned i = 0; i != NumMove; ++i)
           Ops.pop_back();
       } else {
         // This is the new location for the loads / stores.
         MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp;
         while (InsertPos != MBB->end() &&
                (MemOps.count(&*InsertPos) || InsertPos->isDebugValue()))

test/CodeGen/ARM/ldrd.ll

 define i32* @strd_postupdate_inc(i32* %p0, i32 %v0, i32 %v1) "no-frame-pointer-elim"="true" {
   %p0.1 = getelementptr i32, i32* %p0, i32 1
   store i32 %v0, i32* %p0
   store i32 %v1, i32* %p0.1
   %p1 = getelementptr i32, i32* %p0, i32 2
   ret i32* %p1
 }
 
+; CHECK-LABEL: ldrd_strd_aa:
+; NORMAL: ldrd [[TMP1:r[0-9]]], [[TMP2:r[0-9]]],
+; NORMAL: strd [[TMP1]], [[TMP2]],
+; CONSERVATIVE-NOT: ldrd
+; CONSERVATIVE-NOT: strd
+; CHECK: bx lr
+
+define void @ldrd_strd_aa(i32* noalias nocapture %x, i32* noalias nocapture readonly %y) {
+entry:
+  %0 = load i32, i32* %y, align 4
+  store i32 %0, i32* %x, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %y, i32 1
+  %1 = load i32, i32* %arrayidx2, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %x, i32 1
+  store i32 %1, i32* %arrayidx3, align 4
+  ret void
+}
+
 declare void @llvm.lifetime.start(i64, i8* nocapture) nounwind
 declare void @llvm.lifetime.end(i64, i8* nocapture) nounwind

test/CodeGen/ARM/prera-ldst-aliasing.mir

+# RUN: llc -run-pass arm-prera-ldst-opt %s -o - | FileCheck %s
+--- |
+  target triple = "thumbv7---eabi"
+
+  define void @ldrd_strd_aa(i32* noalias nocapture %x, i32* noalias nocapture readonly %y) {
+  entry:
+    %0 = load i32, i32* %y, align 4
+    store i32 %0, i32* %x, align 4
+    %arrayidx2 = getelementptr inbounds i32, i32* %y, i32 1
+    %1 = load i32, i32* %arrayidx2, align 4
+    %arrayidx3 = getelementptr inbounds i32, i32* %x, i32 1
+    store i32 %1, i32* %arrayidx3, align 4
+    ret void
+  }
+...
+---
+name:            ldrd_strd_aa
+alignment:       1
+tracksRegLiveness: true
+liveins:
+  - { reg: '%r0', virtual-reg: '%0' }
+  - { reg: '%r1', virtual-reg: '%1' }
+body:             |
+  bb.0.entry:
+    liveins: %r0, %r1
+
+    %1 : gpr = COPY %r1
+    %0 : gpr = COPY %r0
+    %2 : gpr = t2LDRi12 %1, 0, 14, _ :: (load 4 from %ir.y)
+    t2STRi12 killed %2, %0, 0, 14, _ :: (store 4 into %ir.x)
+    %3 : gpr = t2LDRi12 %1, 4, 14, _ :: (load 4 from %ir.arrayidx2)
+    t2STRi12 killed %3, %0, 4, 14, _ :: (store 4 into %ir.arrayidx3)
+    ; CHECK: t2LDRi12
+    ; CHECK-NEXT: t2LDRi12
+    ; CHECK-NEXT: t2STRi12
+    ; CHECK-NEXT: t2STRi12
+    tBX_RET 14, _
+
+...
+