[LiveIntervals] Find better anchoring end points when repairing ranges

[foad]

Summary

r175673 changed repairIntervalsInRange to find anchoring end points for
ranges automatically, but the calculation of Begin included the first
instruction found that already had an index. This patch changes it to
exclude that instruction:

1. For symmetry, so that the half open range [Begin,End) only includes instructions that do not already have indexes.
2. As a possible performance improvement, since repairOldRegInRange will scan fewer instructions.
3. Because repairOldRegInRange hits assertion failures in some cases when it sees a def that already has a live interval.

(3) fixes about ten tests in the CodeGen lit test suite when
-early-live-intervals is forced on.

[foad]

Add test.

[kparzysz]

llvm/lib/CodeGen/LiveIntervals.cpp

1665

I haven't given this code an in-depth look, but the first thing I noticed is that it gets the preceding iterator: how do we know that std::prev(Begin) is actually valid?

[foad]

llvm/lib/CodeGen/LiveIntervals.cpp

1665

Because of the Begin != MBB->begin() check!

[MatzeB]

Change looks good to me, but I would apreciate a better test.

llvm/lib/CodeGen/LiveIntervals.cpp

1663–1668

Would it be realistic to replace these two loops with an assert() and have the callers perform the adjustments only when necessary?

(just as a suggestions, we don't necessarily need to do this as part of this diff)

llvm/test/CodeGen/Hexagon/mulhs.ll

2

Could you create a test in unittests/MI/LiveIntervalTest.cpp that just does a single call to repairIntervalsInRange instead of having this very indirect form of testing?

[RKSimon]

As @foad mentioned - this patch unblocks D129765 - are we still just waiting on improving test coverage here?

[RKSimon]

It might be that we can reduce the mve-sext-masked-load.ll test regression I hit in D129765 into something suited to LiveIntervalTest.cpp ?

[foad]

Add a unit test distilled from test/CodeGen/Thumb2/mve-sext-masked-load.ll

[MatzeB]

LGTM

llvm/lib/CodeGen/LiveIntervals.cpp

if (!isStartValid && LII->end.isDead())
     LR.removeSegment(*LII, true);
 }
 
 void
 LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
                                       MachineBasicBlock::iterator Begin,
                                       MachineBasicBlock::iterator End,
                                       ArrayRef<Register> OrigRegs) {
   // Find anchor points, which are at the beginning/end of blocks or at
   // instructions that already have indexes.
-  while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin))
+  while (Begin != MBB->begin() && !Indexes->hasIndex(*std::prev(Begin)))
     --Begin;
   while (End != MBB->end() && !Indexes->hasIndex(*End))
     ++End;
 
   SlotIndex EndIdx;
   if (End == MBB->end())
     EndIdx = getMBBEndIdx(MBB).getPrevSlot();
   else
     EndIdx = getInstructionIndex(*End);
 
   Indexes->repairIndexesInRange(MBB, Begin, End);

llvm/lib/CodeGen/SlotIndexes.cpp

LLVM_DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << startItr->getIndex()
                     << '-' << index << " ***\n");
   ++NumLocalRenum;
 }
 
 // Repair indexes after adding and removing instructions.
 void SlotIndexes::repairIndexesInRange(MachineBasicBlock *MBB,
                                        MachineBasicBlock::iterator Begin,
                                        MachineBasicBlock::iterator End) {
-  // FIXME: Is this really necessary? The only caller repairIntervalsForRange()
-  // does the same thing.
-  // Find anchor points, which are at the beginning/end of blocks or at
-  // instructions that already have indexes.
-  while (Begin != MBB->begin() && !hasIndex(*Begin))
-    --Begin;
-  while (End != MBB->end() && !hasIndex(*End))
-    ++End;
-
   bool includeStart = (Begin == MBB->begin());
   SlotIndex startIdx;
   if (includeStart)
     startIdx = getMBBStartIdx(MBB);
   else
-    startIdx = getInstructionIndex(*Begin);
+    startIdx = getInstructionIndex(*--Begin);
 
   SlotIndex endIdx;
   if (End == MBB->end())
     endIdx = getMBBEndIdx(MBB);
   else
     endIdx = getInstructionIndex(*End);
 
   // FIXME: Conceptually, this code is implementing an iterator on MBB that

llvm/test/CodeGen/Hexagon/mulhs.ll

 ; RUN: llc -march=hexagon < %s | FileCheck %s
+; RUN: llc -march=hexagon -early-live-intervals -verify-machineinstrs < %s | FileCheck %s
 
 ; CHECK: mpy
 ; CHECK-NOT: call
 
 target triple = "hexagon"
 
 ; Function Attrs: nounwind
 define i32 @fred(i64 %x, i64 %y, i64* nocapture %z) #0 {

llvm/unittests/MI/LiveIntervalTest.cpp

liveIntervalTest(R"MIR(
     S_BRANCH %bb.1
   bb.1:
     S_NOP 0
 )MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
     testSplitAt(MF, LIS, 0, 0);
   });
 }
 
+TEST(LiveIntervalTest, RepairIntervals) {
+  liveIntervalTest(R"MIR(
+  %1:sgpr_32 = IMPLICIT_DEF
+  dead %2:sgpr_32 = COPY undef %3.sub0:sgpr_128
+  undef %4.sub2:sgpr_128 = COPY %1:sgpr_32
+  %5:sgpr_32 = COPY %4.sub2:sgpr_128
+)MIR", [](MachineFunction &MF, LiveIntervals &LIS) {
+    MachineInstr &Instr1 = getMI(MF, 1, 0);
+    MachineInstr &Instr2 = getMI(MF, 2, 0);
+    MachineInstr &Instr3 = getMI(MF, 3, 0);
+    LIS.RemoveMachineInstrFromMaps(Instr2);
+    MachineBasicBlock *MBB = Instr1.getParent();
+    SmallVector<Register> OrigRegs{
+      Instr1.getOperand(0).getReg(),
+      Instr2.getOperand(0).getReg(),
+      Instr2.getOperand(1).getReg(),
+    };
+    LIS.repairIntervalsInRange(MBB, Instr2, Instr3, OrigRegs);
+  });
+}
+
 int main(int argc, char **argv) {
   ::testing::InitGoogleTest(&argc, argv);
   initLLVM();
   return RUN_ALL_TESTS();
 }