[LiveIntervals] Replace handleMoveIntoBundle

[critson]

Summary

The current handleMoveIntoBundle implementation is unusable,
it attempts to access the slot indexes of bundled instructions.
It also leaves bundled instructions with slot indexes assigned.

Replace handleMoveIntoBundle this with a more explicit
handleMoveIntoNewBundle function which recalculates the live
intervals for all instructions moved into a newly formed bundle,
and removes slot indexes from these instructions.

[critson]

Add basic unit tests.

[qcolombet]

llvm/include/llvm/CodeGen/LiveIntervals.h

318

typo: livenewss

319

Maybe use the \pre marker to make it explicit that these are pre-conditions.

[kariddi]

I wonder if it would make sense to test that the SlotIndex is the same as the one of the bundle header after calling the method.

llvm/include/llvm/CodeGen/LiveIntervals.h

318–322

s/livenewss/liveness/

llvm/lib/CodeGen/LiveIntervals.cpp

1485

Should we check that we are called on a bundled instruction?

[critson]

Fix typos in comments.
Add assertion to check BundleStart is a bundle.
Fix clang-tidy warnings.
Will land this version if pre-merge tests pass.

llvm/include/llvm/CodeGen/LiveIntervals.h

public:
 
     /// Call this method to notify LiveIntervals that instruction \p MI has been
     /// moved within a basic block. This will update the live intervals for all
     /// operands of \p MI. Moves between basic blocks are not supported.
     ///
     /// \param UpdateFlags Update live intervals for nonallocatable physregs.
     void handleMove(MachineInstr &MI, bool UpdateFlags = false);
 
-    /// Update intervals for operands of \p MI so that they begin/end on the
-    /// SlotIndex for \p BundleStart.
+    /// Update intervals of operands of all instructions in the newly
+    /// created bundle specified by \p BundleStart.
     ///
     /// \param UpdateFlags Update live intervals for nonallocatable physregs.
     ///
-    /// Requires MI and BundleStart to have SlotIndexes, and assumes
-    /// existing liveness is accurate. BundleStart should be the first
-    /// instruction in the Bundle.
-    void handleMoveIntoBundle(MachineInstr &MI, MachineInstr &BundleStart,
+    /// Assumes existing livenewss is accurate.
+    /// BundleStart should be the first instruction in the Bundle.
+    /// BundleStart should not have a have SlotIndex as one will be assigned.
+    void handleMoveIntoNewBundle(MachineInstr &BundleStart,
                                  bool UpdateFlags = false);
 
     /// Update live intervals for instructions in a range of iterators. It is
     /// intended for use after target hooks that may insert or remove
     /// instructions, and is only efficient for a small number of instructions.
     ///
     /// OrigRegs is a vector of registers that were originally used by the
     /// instructions in the range between the two iterators.
     ///

llvm/include/llvm/CodeGen/SlotIndexes.h

public:
 
     /// Returns true if the given machine instr is mapped to an index,
     /// otherwise returns false.
     bool hasIndex(const MachineInstr &instr) const {
       return mi2iMap.count(&instr);
     }
 
     /// Returns the base index for the given instruction.
-    SlotIndex getInstructionIndex(const MachineInstr &MI) const {
+    SlotIndex getInstructionIndex(const MachineInstr &MI,
+                                  bool IgnoreBundle = false) const {
       // Instructions inside a bundle have the same number as the bundle itself.
       auto BundleStart = getBundleStart(MI.getIterator());
       auto BundleEnd = getBundleEnd(MI.getIterator());
       // Use the first non-debug instruction in the bundle to get SlotIndex.
       const MachineInstr &BundleNonDebug =
-          *skipDebugInstructionsForward(BundleStart, BundleEnd);
+          IgnoreBundle ? MI
+                       : *skipDebugInstructionsForward(BundleStart, BundleEnd);
       assert(!BundleNonDebug.isDebugInstr() &&
              "Could not use a debug instruction to query mi2iMap.");
       Mi2IndexMap::const_iterator itr = mi2iMap.find(&BundleNonDebug);
       assert(itr != mi2iMap.end() && "Instruction not found in maps.");
       return itr->second;
     }
 
     /// Returns the instruction for the given index, or null if the given
SlotIndex insertMachineInstrInMaps(MachineInstr &MI, bool Late = false) {
       SlotIndex newIndex(&*newItr, SlotIndex::Slot_Block);
       mi2iMap.insert(std::make_pair(&MI, newIndex));
       return newIndex;
     }
 
     /// Removes machine instruction (bundle) \p MI from the mapping.
     /// This should be called before MachineInstr::eraseFromParent() is used to
     /// remove a whole bundle or an unbundled instruction.
-    void removeMachineInstrFromMaps(MachineInstr &MI);
+    /// If \p AllowBundled is set then this can be used on a bundled
+    /// instruction; however, this exists to support handleMoveIntoBundle,
+    /// and in general removeSingleMachineInstrFromMaps should be used instead.
+    void removeMachineInstrFromMaps(MachineInstr &MI,
+                                    bool AllowBundled = false);
 
     /// Removes a single machine instruction \p MI from the mapping.
     /// This should be called before MachineInstr::eraseFromBundle() is used to
     /// remove a single instruction (out of a bundle).
     void removeSingleMachineInstrFromMaps(MachineInstr &MI);
 
     /// ReplaceMachineInstrInMaps - Replacing a machine instr with a new one in
     /// maps used by register allocator. \returns the index where the new

llvm/lib/CodeGen/LiveIntervals.cpp

void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
   assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
          OldIndex < getMBBEndIdx(MI.getParent()) &&
          "Cannot handle moves across basic block boundaries.");
 
   HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
   HME.updateAllRanges(&MI);
 }
 
-void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI,
-                                         MachineInstr &BundleStart,
+void LiveIntervals::handleMoveIntoNewBundle(MachineInstr &BundleStart,
                                             bool UpdateFlags) {
-  SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
-  SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
+  SmallVector<SlotIndex, 16> ToProcess;
+  const SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(BundleStart);
+  auto BundleEnd = getBundleEnd(BundleStart.getIterator());
+
+  auto I = BundleStart.getIterator();
+  I++;
+  while (I != BundleEnd) {
+    if (!Indexes->hasIndex(*I))
+      continue;
+    SlotIndex OldIndex = Indexes->getInstructionIndex(*I, true);
+    ToProcess.push_back(OldIndex);
+    Indexes->removeMachineInstrFromMaps(*I, true);
+    I++;
+  }
+  for (SlotIndex OldIndex : ToProcess) {
     HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
-  HME.updateAllRanges(&MI);
+    HME.updateAllRanges(&BundleStart);
+  }
 }
 
 void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
                                         const MachineBasicBlock::iterator End,
                                         const SlotIndex endIdx,
                                         LiveRange &LR, const unsigned Reg,
                                         LaneBitmask LaneMask) {
   LiveInterval::iterator LII = LR.find(endIdx);

llvm/lib/CodeGen/SlotIndexes.cpp

bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
   llvm::sort(idx2MBBMap, less_first());
 
   LLVM_DEBUG(mf->print(dbgs(), this));
 
   // And we're done!
   return false;
 }
 
-void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI) {
-  assert(!MI.isBundledWithPred() &&
-         "Use removeSingleMachineInstrFromMaps() instread");
+void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI,
+                                             bool AllowBundled) {
+  assert((AllowBundled || !MI.isBundledWithPred()) &&
+         "Use removeSingleMachineInstrFromMaps() instead");
   Mi2IndexMap::iterator mi2iItr = mi2iMap.find(&MI);
   if (mi2iItr == mi2iMap.end())
     return;
 
   SlotIndex MIIndex = mi2iItr->second;
   IndexListEntry &MIEntry = *MIIndex.listEntry();
   assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
   mi2iMap.erase(mi2iItr);
void SlotIndexes::removeSingleMachineInstrFromMaps(MachineInstr &MI) {
   IndexListEntry &MIEntry = *MIIndex.listEntry();
   assert(MIEntry.getInstr() == &MI && "Instruction indexes broken.");
   mi2iMap.erase(mi2iItr);
 
   // When removing the first instruction of a bundle update mapping to next
   // instruction.
   if (MI.isBundledWithSucc()) {
     // Only the first instruction of a bundle should have an index assigned.
-    assert(!MI.isBundledWithPred() && "Should have first bundle isntruction");
+    assert(!MI.isBundledWithPred() && "Should be first bundle instruction");
 
     MachineBasicBlock::instr_iterator Next = std::next(MI.getIterator());
     MachineInstr &NextMI = *Next;
     MIEntry.setInstr(&NextMI);
     mi2iMap.insert(std::make_pair(&NextMI, MIIndex));
     return;
   } else {
     // FIXME: Eventually we want to actually delete these indexes.