[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–322

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 liveness is accurate.
+    /// \pre BundleStart should be the first instruction in the Bundle.
+    /// \pre 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);
+  assert((BundleStart.getOpcode() == TargetOpcode::BUNDLE) &&
+         "Bundle start is not a bundle");
+  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);
+  }
+
+  // Fix up dead defs
+  const SlotIndex Index = getInstructionIndex(BundleStart);
+  for (unsigned Idx = 0, E = BundleStart.getNumOperands(); Idx != E; ++Idx) {
+    MachineOperand &MO = BundleStart.getOperand(Idx);
+    if (!MO.isReg())
+      continue;
+    Register Reg = MO.getReg();
+    if (Reg.isVirtual() && hasInterval(Reg) && !MO.isUndef()) {
+      LiveInterval &LI = getInterval(Reg);
+      LiveQueryResult LRQ = LI.Query(Index);
+      if (LRQ.isDeadDef())
+        MO.setIsDead();
+    }
+  }
 }
 
 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.

llvm/unittests/MI/LiveIntervalTest.cpp

static void testHandleMove(MachineFunction &MF, LiveIntervals &LIS,
   MachineInstr &FromInstr = getMI(MF, From, BlockNum);
   MachineInstr &ToInstr = getMI(MF, To, BlockNum);
 
   MachineBasicBlock &MBB = *FromInstr.getParent();
   MBB.splice(ToInstr.getIterator(), &MBB, FromInstr.getIterator());
   LIS.handleMove(FromInstr, true);
 }
 
+/**
+ * Move instructions numbered \p From inclusive through instruction number
+ * \p To into a newly formed bundle and update affected liveness intervals
+ * with LiveIntervalAnalysis::handleMoveIntoNewBundle().
+ */
+static void testHandleMoveIntoNewBundle(MachineFunction &MF, LiveIntervals &LIS,
+                                        unsigned From, unsigned To,
+                                        unsigned BlockNum = 0) {
+  MachineInstr &FromInstr = getMI(MF, From, BlockNum);
+  MachineInstr &ToInstr = getMI(MF, To, BlockNum);
+  MachineBasicBlock &MBB = *FromInstr.getParent();
+  MachineBasicBlock::instr_iterator I = FromInstr.getIterator();
+
+  // Build bundle
+  finalizeBundle(MBB, I, std::next(ToInstr.getIterator()));
+
+  // Update LiveIntervals
+  MachineBasicBlock::instr_iterator BundleStart = std::prev(I);
+  LIS.handleMoveIntoNewBundle(*BundleStart, true);
+}
+
 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;

 
 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
      MachineInstr &UndefSubregDef = getMI(MF, 2, 1);
      // The scheduler clears undef from subregister defs before moving
      UndefSubregDef.getOperand(0).setIsUndef(false);
      testHandleMove(MF, LIS, 4, 1, 1);
   });
 }
+
+TEST(LiveIntervalTest, BundleUse) {
+  liveIntervalTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0
+    S_NOP 0, implicit %0
+    S_NOP 0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testHandleMoveIntoNewBundle(MF, LIS, 1, 2);
+  });
+}
+
+TEST(LiveIntervalTest, BundleDef) {
+  liveIntervalTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0
+    S_NOP 0, implicit %0
+    S_NOP 0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testHandleMoveIntoNewBundle(MF, LIS, 0, 1);
+  });
+}
+
+TEST(LiveIntervalTest, BundleRedef) {
+  liveIntervalTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0
+    %0 = IMPLICIT_DEF implicit %0(tied-def 0)
+    S_NOP 0, implicit %0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testHandleMoveIntoNewBundle(MF, LIS, 1, 2);
+  });
+}
+
+TEST(LiveIntervalTest, BundleInternalUse) {
+  liveIntervalTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0
+    S_NOP 0, implicit %0
+    S_NOP 0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testHandleMoveIntoNewBundle(MF, LIS, 0, 2);
+  });
+}
+
+TEST(LiveIntervalTest, BundleUndefUse) {
+  liveIntervalTest(R"MIR(
+    %0 = IMPLICIT_DEF
+    S_NOP 0
+    S_NOP 0, implicit undef %0
+    S_NOP 0
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testHandleMoveIntoNewBundle(MF, LIS, 1, 2);
+  });
+}
+
+TEST(LiveIntervalTest, BundleSubRegUse) {
+  liveIntervalTest(R"MIR(
+    successors: %bb.1, %bb.2
+    undef %0.sub0 = IMPLICIT_DEF
+    %0.sub1 = IMPLICIT_DEF
+    S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
+    S_BRANCH %bb.1
+  bb.1:
+    S_NOP 0
+    S_NOP 0, implicit %0.sub1
+  bb.2:
+    S_NOP 0, implicit %0.sub1
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    testHandleMoveIntoNewBundle(MF, LIS, 0, 1, 1);
+  });
+}
+
+TEST(LiveIntervalTest, BundleSubRegDef) {
+  liveIntervalTest(R"MIR(
+    successors: %bb.1, %bb.2
+    undef %0.sub0 = IMPLICIT_DEF
+    %0.sub1 = IMPLICIT_DEF
+    S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
+    S_BRANCH %bb.1
+  bb.1:
+    S_NOP 0
+    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);
+  });
+}
+
 int main(int argc, char **argv) {
   ::testing::InitGoogleTest(&argc, argv);
   initLLVM();
   return RUN_ALL_TESTS();
 }