AMDGPU: Add check to recompute merge-able instructions

[dstuttard]

Summary

When SILoadStoreOptimizer merges instructions, if an instruction from a
different set of merge-able instructions is moved, this invalidates the yet to be
processed list. This change can detect this situation and forces a re-computation
of the yet to be processed instructions.

This is likely to be a relatively rare occurrence, so the extra overhead of the
computation is negligible.

Change-Id: Ie6d26596fea2af03b0dd5e029d74281079930ad2

[dstuttard]

I encountered this issue with a test shader I was looking at. I did manage to create a reproducer, but a different fix to the triviallyDisjoint function meant that it stopped happening.
However, I still think the situation may occur, hence putting this change up for review.

If the consensus is that it is valid, I can try to create a test case for it.

[dstuttard]

Formatting fixes

[dstuttard]

Added more reviewers - anyone got an opinion on this one.

I'm now wondering if it might be possible to use a different approach that doesn't use iterators. Any thoughts?

[tstellar]

How would it invalidate the list? Isn't the analysis of which instructions can be moved done one list at a time?

[dstuttard]

In D75741#1926383, @tstellar wrote:

How would it invalidate the list? Isn't the analysis of which instructions can be moved done one list at a time?

My impression (perhaps incorrect) was that the original code built a list of lists of instructions in a block that can be optimised.
My change keeps a list of instructions that have been moved when processing one list - and if those instructions are found in another unprocessed list it sets an invalid flag. This forces a re-computation of the un-optimised instructions thus making the iterators valid again. I thought this wouldn't be too expensive as I suspect this very rarely happens (hence the reason that we haven't picked up the problem before now).

[arsenm]

Is this still necessary?

llvm/lib/Target/AMDGPU/SILoadStoreOptimizer.cpp

 private:
   const GCNSubtarget *STM = nullptr;
   const SIInstrInfo *TII = nullptr;
   const SIRegisterInfo *TRI = nullptr;
   const MCSubtargetInfo *STI = nullptr;
   MachineRegisterInfo *MRI = nullptr;
   AliasAnalysis *AA = nullptr;
   bool OptimizeAgain;
+  bool MergeableInvalid;
+  std::set<MachineInstr*> MIMovedList;
 
   static bool dmasksCanBeCombined(const CombineInfo &CI,
                                   const SIInstrInfo &TII,
                                   const CombineInfo &Paired);
   static bool offsetsCanBeCombined(CombineInfo &CI, const MCSubtargetInfo &STI,
                                    CombineInfo &Paired, bool Modify = false);
   static bool widthsFit(const GCNSubtarget &STM, const CombineInfo &CI,
                         const CombineInfo &Paired);
private:
   bool promoteConstantOffsetToImm(MachineInstr &CI,
                                   MemInfoMap &Visited,
                                   SmallPtrSet<MachineInstr *, 4> &Promoted) const;
   void addInstToMergeableList(const CombineInfo &CI,
                   std::list<std::list<CombineInfo> > &MergeableInsts) const;
   bool collectMergeableInsts(MachineBasicBlock &MBB,
                   std::list<std::list<CombineInfo> > &MergeableInsts) const;
 
+  bool isCleanMergeList(std::list<CombineInfo> &MergeList) const;
+
 public:
   static char ID;
 
   SILoadStoreOptimizer() : MachineFunctionPass(ID) {
     initializeSILoadStoreOptimizerPass(*PassRegistry::getPassRegistry());
   }
 
   bool optimizeInstsWithSameBaseAddr(std::list<CombineInfo> &MergeList,
                                      bool &OptimizeListAgain);
-  bool optimizeBlock(std::list<std::list<CombineInfo> > &MergeableInsts);
+  bool optimizeBlock(std::list<std::list<CombineInfo> > &MergeableInsts,
+                     MachineBasicBlock &MBB);
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   StringRef getPassName() const override { return "SI Load Store Optimizer"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AAResultsWrapperPass>();

 
 char &llvm::SILoadStoreOptimizerID = SILoadStoreOptimizer::ID;
 
 FunctionPass *llvm::createSILoadStoreOptimizerPass() {
   return new SILoadStoreOptimizer();
 }
 
 static void moveInstsAfter(MachineBasicBlock::iterator I,
-                           ArrayRef<MachineInstr *> InstsToMove) {
+                           ArrayRef<MachineInstr *> InstsToMove,
+                           std::set<MachineInstr*> &MovedList) {
   MachineBasicBlock *MBB = I->getParent();
   ++I;
   for (MachineInstr *MI : InstsToMove) {
     MI->removeFromParent();
     MBB->insert(I, MI);
+    MovedList.insert(MI);
   }
 }
 
 static void addDefsUsesToList(const MachineInstr &MI,
                               DenseSet<unsigned> &RegDefs,
                               DenseSet<unsigned> &PhysRegUses) {
   for (const MachineOperand &Op : MI.operands()) {
     if (Op.isReg()) {
SILoadStoreOptimizer::mergeRead2Pair(CombineInfo &CI, CombineInfo &Paired,
   // Copy to the old destination registers.
   BuildMI(*MBB, Paired.I, DL, CopyDesc)
       .add(*Dest0) // Copy to same destination including flags and sub reg.
       .addReg(DestReg, 0, SubRegIdx0);
   MachineInstr *Copy1 = BuildMI(*MBB, Paired.I, DL, CopyDesc)
                             .add(*Dest1)
                             .addReg(DestReg, RegState::Kill, SubRegIdx1);
 
-  moveInstsAfter(Copy1, InstsToMove);
+  moveInstsAfter(Copy1, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
 
   LLVM_DEBUG(dbgs() << "Inserted read2: " << *Read2 << '\n');
   return Read2;
 }
 
MachineInstrBuilder Write2 =
           .addReg(BaseReg, BaseRegFlags, BaseSubReg) // addr
           .add(*Data0)                               // data0
           .add(*Data1)                               // data1
           .addImm(NewOffset0)                        // offset0
           .addImm(NewOffset1)                        // offset1
           .addImm(0)                                 // gds
           .cloneMergedMemRefs({&*CI.I, &*Paired.I});
 
-  moveInstsAfter(Write2, InstsToMove);
+  moveInstsAfter(Write2, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
 
   LLVM_DEBUG(dbgs() << "Inserted write2 inst: " << *Write2 << '\n');
   return Write2;
 }
 
SILoadStoreOptimizer::mergeImagePair(CombineInfo &CI, CombineInfo &Paired,
 
   BuildMI(*MBB, Paired.I, DL, CopyDesc)
       .add(*Dest0) // Copy to same destination including flags and sub reg.
       .addReg(DestReg, 0, SubRegIdx0);
   MachineInstr *Copy1 = BuildMI(*MBB, Paired.I, DL, CopyDesc)
                             .add(*Dest1)
                             .addReg(DestReg, RegState::Kill, SubRegIdx1);
 
-  moveInstsAfter(Copy1, InstsToMove);
+  moveInstsAfter(Copy1, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
   return New;
 }
 
 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeSBufferLoadImmPair(
     CombineInfo &CI, CombineInfo &Paired,
MachineBasicBlock::iterator SILoadStoreOptimizer::mergeSBufferLoadImmPair(
 
   BuildMI(*MBB, Paired.I, DL, CopyDesc)
       .add(*Dest0) // Copy to same destination including flags and sub reg.
       .addReg(DestReg, 0, SubRegIdx0);
   MachineInstr *Copy1 = BuildMI(*MBB, Paired.I, DL, CopyDesc)
                             .add(*Dest1)
                             .addReg(DestReg, RegState::Kill, SubRegIdx1);
 
-  moveInstsAfter(Copy1, InstsToMove);
+  moveInstsAfter(Copy1, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
   return New;
 }
 
 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeBufferLoadPair(
     CombineInfo &CI, CombineInfo &Paired,
MachineBasicBlock::iterator SILoadStoreOptimizer::mergeBufferLoadPair(
 
   BuildMI(*MBB, Paired.I, DL, CopyDesc)
       .add(*Dest0) // Copy to same destination including flags and sub reg.
       .addReg(DestReg, 0, SubRegIdx0);
   MachineInstr *Copy1 = BuildMI(*MBB, Paired.I, DL, CopyDesc)
                             .add(*Dest1)
                             .addReg(DestReg, RegState::Kill, SubRegIdx1);
 
-  moveInstsAfter(Copy1, InstsToMove);
+  moveInstsAfter(Copy1, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
   return New;
 }
 
 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeTBufferLoadPair(
     CombineInfo &CI, CombineInfo &Paired,
MachineBasicBlock::iterator SILoadStoreOptimizer::mergeTBufferLoadPair(
 
   BuildMI(*MBB, Paired.I, DL, CopyDesc)
       .add(*Dest0) // Copy to same destination including flags and sub reg.
       .addReg(DestReg, 0, SubRegIdx0);
   MachineInstr *Copy1 = BuildMI(*MBB, Paired.I, DL, CopyDesc)
                             .add(*Dest1)
                             .addReg(DestReg, RegState::Kill, SubRegIdx1);
 
-  moveInstsAfter(Copy1, InstsToMove);
+  moveInstsAfter(Copy1, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
   return New;
 }
 
 MachineBasicBlock::iterator SILoadStoreOptimizer::mergeTBufferStorePair(
     CombineInfo &CI, CombineInfo &Paired,
MachineInstr *New =
           .addImm(CI.GLC)                          // glc
           .addImm(CI.SLC)                          // slc
           .addImm(0)                                // tfe
           .addImm(CI.DLC)                          // dlc
           .addImm(0)                                // swz
           .addMemOperand(
               combineKnownAdjacentMMOs(*MBB->getParent(), MMOa, MMOb));
 
-  moveInstsAfter(MIB, InstsToMove);
+  moveInstsAfter(MIB, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
   return New;
 }
 
 unsigned SILoadStoreOptimizer::getNewOpcode(const CombineInfo &CI,
                                             const CombineInfo &Paired) {
MIB.add(*TII->getNamedOperand(*CI.I, AMDGPU::OpName::srsrc))
         .addImm(std::min(CI.Offset, Paired.Offset)) // offset
         .addImm(CI.GLC)      // glc
         .addImm(CI.SLC)      // slc
         .addImm(0)            // tfe
         .addImm(CI.DLC)      // dlc
         .addImm(0)            // swz
         .addMemOperand(combineKnownAdjacentMMOs(*MBB->getParent(), MMOa, MMOb));
 
-  moveInstsAfter(MIB, InstsToMove);
+  moveInstsAfter(MIB, InstsToMove, MIMovedList);
 
   CI.I->eraseFromParent();
   Paired.I->eraseFromParent();
   return New;
 }
 
 MachineOperand
 SILoadStoreOptimizer::createRegOrImm(int32_t Val, MachineInstr &MI) const {
MergeList.sort(
           return A.Offset < B.Offset;
         });
     ++I;
   }
 
   return Modified;
 }
 
+bool SILoadStoreOptimizer::isCleanMergeList(std::list<CombineInfo> &MergeList) const {
+  for (auto I : MergeList) {
+    MachineInstr* MI = &*(I.I);
+    if (MIMovedList.count(MI))
+      return false;
+  }
+  return true;
+}
+
 // Scan through looking for adjacent LDS operations with constant offsets from
 // the same base register. We rely on the scheduler to do the hard work of
 // clustering nearby loads, and assume these are all adjacent.
 bool SILoadStoreOptimizer::optimizeBlock(
-                       std::list<std::list<CombineInfo> > &MergeableInsts) {
+                       std::list<std::list<CombineInfo> > &MergeableInsts,
+                       MachineBasicBlock &MBB) {
   bool Modified = false;
 
   for (std::list<std::list<CombineInfo>>::iterator I = MergeableInsts.begin(),
                                                    E = MergeableInsts.end(); I != E;) {
     std::list<CombineInfo> &MergeList = *I;
 
+    if (!isCleanMergeList(MergeList)) {
+      MergeableInvalid = true;
+      return Modified;
+    }
+
     bool OptimizeListAgain = false;
     if (!optimizeInstsWithSameBaseAddr(MergeList, OptimizeListAgain)) {
       // We weren't able to make any changes, so delete the list so we don't
       // process the same instructions the next time we try to optimize this
       // block.
       I = MergeableInsts.erase(I);
       continue;
     }
bool SILoadStoreOptimizer::runOnMachineFunction(MachineFunction &MF) {
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   assert(MRI->isSSA() && "Must be run on SSA");
 
   LLVM_DEBUG(dbgs() << "Running SILoadStoreOptimizer\n");
 
   bool Modified = false;
 
-
   for (MachineBasicBlock &MBB : MF) {
-    std::list<std::list<CombineInfo> > MergeableInsts;
     // First pass: Collect list of all instructions we know how to merge.
+    do {
+      std::list<std::list<CombineInfo> > MergeableInsts;
       Modified |= collectMergeableInsts(MBB, MergeableInsts);
+      MergeableInvalid = false;
+      MIMovedList.clear();
+
       do {
         OptimizeAgain = false;
-      Modified |= optimizeBlock(MergeableInsts);
-    } while (OptimizeAgain);
+        Modified |= optimizeBlock(MergeableInsts, MBB);
+      } while (OptimizeAgain && !MergeableInvalid);
+
+      // Has a transformation occurred that invalidates the MergeableInsts list?
+      // This can happen if other mergeable instructions are moved when merging
+      // a different list
+    } while(MergeableInvalid);
   }
 
   return Modified;
 }