[SlotIndexes] Add insertion point for insertMBBIntoMaps

[critson]

Summary

Allow the specification of an insertion point (MachineInstr)
for insertMBBIntoMaps.
This makes it possible to update slot indexes and live intervals
when trivially splitting a block by specifying the point of the
split as the insertion point for the block in the maps.

[kariddi]

I don't get completely what is the difference between this and just calling insertMBBInMaps() with the new block created by split as the argument. Shouldn't the insertion point being automatically devised correctly if the block is inserted in the right position?

llvm/include/llvm/CodeGen/SlotIndexes.h

609

It seems it is actually put "before the next block in MachineFunction insertion order" (I don't think it has anything to do with it being a predecessor or a successor).

[critson]

In D78417#1993083, @kariddi wrote:

I don't get completely what is the difference between this and just calling insertMBBInMaps() with the new block created by split as the argument. Shouldn't the insertion point being automatically devised correctly if the block is inserted in the right position?

I think the best way to describe the difference is that, at present, insertMBBInMaps inserts the block between blocks, but for splitting we need to the ability to insert the block between instructions. When splitting a sequence of instructions which already have slot indexes, the block needs to come before a given instruction, rather than the next block (which is after the instructions in the new block).

An alternative implementation to the one in this patch would be to change insertMBBInMaps so that it checks if first instruction of the block being added has a slot index. If so, then the block should go before that index, otherwise the current behaviour is maintained, i.e. for new empty blocks, or new blocks of new instructions.

[kariddi]

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) {
-      Indexes->insertMBBInMaps(MBB);
+    void insertMBBInMaps(MachineBasicBlock *MBB,
+                         MachineInstr *InsertionPoint = nullptr) {
+      Indexes->insertMBBInMaps(MBB, InsertionPoint);
       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.
-    void insertMBBInMaps(MachineBasicBlock *mbb) {
+    /// If \p InsertionPoint is specified then the block will be placed
+    /// before the given machine instr, otherwise it will be placed
+    /// immediately following the block's predecessor.
+    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 (nextMBB == mbb->getParent()->end()) {
+      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);
       }