[SlotIndexes] Fix and simplify basic block splitting

[foad]

Summary

Remove the InsertionPoint argument from SlotIndexes::insertMBBInMaps
because it was confusing: what does it mean to insert a new block
between two instructions, in the middle of an existing block?

Instead, support the case that MachineBasicBlock::splitAt really needs,
where the new block contains some instructions that are already in the
maps because they have been moved there from the tail of the previous
block.

In all other use cases the new block is empty.

Based on work by Carl Ritson!

[foad]

This is intended to supersede D91066 and D91064.

[critson]

LGTM

llvm/include/llvm/CodeGen/LiveIntervals.h

bool isLiveOutOfMBB(const LiveRange &LR,
                         const MachineBasicBlock *mbb) const {
       return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot());
     }
 
     MachineBasicBlock* getMBBFromIndex(SlotIndex index) const {
       return Indexes->getMBBFromIndex(index);
     }
 
-    void insertMBBInMaps(MachineBasicBlock *MBB,
-                         MachineInstr *InsertionPoint = nullptr) {
-      Indexes->insertMBBInMaps(MBB, InsertionPoint);
+    void insertMBBInMaps(MachineBasicBlock *MBB) {
+      Indexes->insertMBBInMaps(MBB);
       assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() &&
              "Blocks must be added in order.");
       RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0));
     }
 
     SlotIndex InsertMachineInstrInMaps(MachineInstr &MI) {
       return Indexes->insertMachineInstrInMaps(MI);
     }

llvm/include/llvm/CodeGen/SlotIndexes.h

SlotIndex replaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) {
              "Mismatched instruction in index tables.");
       miEntry->setInstr(&NewMI);
       mi2iMap.erase(mi2iItr);
       mi2iMap.insert(std::make_pair(&NewMI, replaceBaseIndex));
       return replaceBaseIndex;
     }
 
     /// Add the given MachineBasicBlock into the maps.
-    /// If \p InsertionPoint is specified then the block will be placed
-    /// before the given machine instr, otherwise it will be placed
-    /// before the next block in MachineFunction insertion order.
-    void insertMBBInMaps(MachineBasicBlock *mbb,
-                         MachineInstr *InsertionPoint = nullptr) {
-      MachineFunction::iterator nextMBB =
-        std::next(MachineFunction::iterator(mbb));
-
-      IndexListEntry *startEntry = nullptr;
-      IndexListEntry *endEntry = nullptr;
-      IndexList::iterator newItr;
-      if (InsertionPoint) {
-        startEntry = createEntry(nullptr, 0);
-        endEntry = getInstructionIndex(*InsertionPoint).listEntry();
-        newItr = indexList.insert(endEntry->getIterator(), startEntry);
-      } else if (nextMBB == mbb->getParent()->end()) {
-        startEntry = &indexList.back();
-        endEntry = createEntry(nullptr, 0);
-        newItr = indexList.insertAfter(startEntry->getIterator(), endEntry);
-      } else {
-        startEntry = createEntry(nullptr, 0);
-        endEntry = getMBBStartIdx(&*nextMBB).listEntry();
-        newItr = indexList.insert(endEntry->getIterator(), startEntry);
-      }
+    /// If it contains any instructions then they must already be in the maps.
+    /// This is used after a block has been split by moving some suffix of its
+    /// instructions into a newly created block.
+    void insertMBBInMaps(MachineBasicBlock *mbb) {
+      assert(mbb != &mbb->getParent()->front() &&
+             "Can't insert a new block at the beginning of a function.");
+      auto prevMBB = std::prev(MachineFunction::iterator(mbb));
+
+      // Create a new entry to be used for the start of mbb and the end of
+      // prevMBB.
+      IndexListEntry *startEntry = createEntry(nullptr, 0);
+      IndexListEntry *endEntry = getMBBEndIdx(&*prevMBB).listEntry();
+      IndexListEntry *insEntry =
+          mbb->empty() ? endEntry
+                       : getInstructionIndex(mbb->front()).listEntry();
+      IndexList::iterator newItr =
+          indexList.insert(insEntry->getIterator(), startEntry);
 
       SlotIndex startIdx(startEntry, SlotIndex::Slot_Block);
       SlotIndex endIdx(endEntry, SlotIndex::Slot_Block);
 
-      MachineFunction::iterator prevMBB(mbb);
-      assert(prevMBB != mbb->getParent()->end() &&
-             "Can't insert a new block at the beginning of a function.");
-      --prevMBB;
       MBBRanges[prevMBB->getNumber()].second = startIdx;
 
       assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
              "Blocks must be added in order");
       MBBRanges.push_back(std::make_pair(startIdx, endIdx));
       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
 
       renumberIndexes(newItr);

llvm/lib/CodeGen/MachineBasicBlock.cpp

MachineBasicBlock *MachineBasicBlock::splitAt(MachineInstr &MI,
 
   SplitBB->transferSuccessorsAndUpdatePHIs(this);
   addSuccessor(SplitBB);
 
   if (UpdateLiveIns)
     addLiveIns(*SplitBB, LiveRegs);
 
   if (LIS)
-    LIS->insertMBBInMaps(SplitBB, &MI);
+    LIS->insertMBBInMaps(SplitBB);
 
   return SplitBB;
 }
 
 MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(
     MachineBasicBlock *Succ, Pass &P,
     std::vector<SparseBitVector<>> *LiveInSets) {
   if (!canSplitCriticalEdge(Succ))

llvm/unittests/MI/LiveIntervalTest.cpp

static void testHandleMoveIntoNewBundle(MachineFunction &MF, LiveIntervals &LIS,
   // Build bundle
   finalizeBundle(MBB, I, std::next(ToInstr.getIterator()));
 
   // Update LiveIntervals
   MachineBasicBlock::instr_iterator BundleStart = std::prev(I);
   LIS.handleMoveIntoNewBundle(*BundleStart, true);
 }
 
+/**
+ * Split block numbered \p BlockNum at instruction \p SplitAt using
+ * MachineBasicBlock::splitAt updating liveness intervals.
+ */
+static void testSplitAt(MachineFunction &MF, LiveIntervals &LIS,
+                        unsigned SplitAt, unsigned BlockNum) {
+  MachineInstr &SplitInstr = getMI(MF, SplitAt, BlockNum);
+  MachineBasicBlock &MBB = *SplitInstr.getParent();
+
+  // Split block and update live intervals
+  MBB.splitAt(SplitInstr, false, &LIS);
+}
+
 static void liveIntervalTest(StringRef MIRFunc, LiveIntervalTest T) {
   LLVMContext Context;
   std::unique_ptr<LLVMTargetMachine> TM = createTargetMachine();
   // This test is designed for the X86 backend; stop if it is not available.
   if (!TM)
     return;
 
   legacy::PassManager PM;
bb.1:
     S_NOP 0, implicit %0.sub1
   bb.2:
     S_NOP 0, implicit %0.sub1
 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
     testHandleMoveIntoNewBundle(MF, LIS, 0, 1, 0);
   });
 }
 
+TEST(LiveIntervalTest, SplitAtOneInstruction) {
+  liveIntervalTest(R"MIR(
+    successors: %bb.1
+    %0 = IMPLICIT_DEF
+    S_BRANCH %bb.1
+  bb.1:
+    S_NOP 0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testSplitAt(MF, LIS, 1, 0);
+  });
+}
+
+TEST(LiveIntervalTest, SplitAtMultiInstruction) {
+  liveIntervalTest(R"MIR(
+    successors: %bb.1
+    %0 = IMPLICIT_DEF
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_NOP 0
+    S_BRANCH %bb.1
+  bb.1:
+    S_NOP 0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testSplitAt(MF, LIS, 0, 0);
+  });
+}
+
 int main(int argc, char **argv) {
   ::testing::InitGoogleTest(&argc, argv);
   initLLVM();
   return RUN_ALL_TESTS();
 }