SplitKit: Remove decade old live interval hack

[arsenm]

Summary

This was trying to fixup broken live intervals coming out of the
coalescer. The verifier is more complete now and no tests seem to fail
without this.

[qcolombet]

LGTM

[arsenm]

87c00878d3ace60fe07cc2a9f8bd4566ab817d26

llvm/lib/CodeGen/RegAllocGreedy.cpp

if (LIS->intervalIsInOneMBB(VirtReg)) {
     return tryInstructionSplit(VirtReg, Order, NewVRegs);
   }
 
   NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,
                      TimerGroupDescription, TimePassesIsEnabled);
 
   SA->analyze(&VirtReg);
 
-  // FIXME: SplitAnalysis may repair broken live ranges coming from the
-  // coalescer. That may cause the range to become allocatable which means that
-  // tryRegionSplit won't be making progress. This check should be replaced with
-  // an assertion when the coalescer is fixed.
-  if (SA->didRepairRange()) {
-    // VirtReg has changed, so all cached queries are invalid.
-    Matrix->invalidateVirtRegs();
-    if (Register PhysReg = tryAssign(VirtReg, Order, NewVRegs, FixedRegisters))
-      return PhysReg;
-  }
-
   // First try to split around a region spanning multiple blocks. RS_Split2
   // ranges already made dubious progress with region splitting, so they go
   // straight to single block splitting.
   if (getStage(VirtReg) < RS_Split2) {
     MCRegister PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
     if (PhysReg || !NewVRegs.empty())
       return PhysReg;
   }

llvm/lib/CodeGen/SplitKit.h

private:
   unsigned NumGapBlocks;
 
   /// ThroughBlocks - Block numbers where CurLI is live through without uses.
   BitVector ThroughBlocks;
 
   /// NumThroughBlocks - Number of live-through blocks.
   unsigned NumThroughBlocks;
 
-  /// DidRepairRange - analyze was forced to shrinkToUses().
-  bool DidRepairRange;
-
   // Sumarize statistics by counting instructions using CurLI.
   void analyzeUses();
 
   /// calcLiveBlockInfo - Compute per-block information about CurLI.
-  bool calcLiveBlockInfo();
+  void calcLiveBlockInfo();
 
 public:
   SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
                 const MachineLoopInfo &mli);
 
   /// analyze - set CurLI to the specified interval, and analyze how it may be
   /// split.
   void analyze(const LiveInterval *li);
 
-  /// didRepairRange() - Returns true if CurLI was invalid and has been repaired
-  /// by analyze(). This really shouldn't happen, but sometimes the coalescer
-  /// can create live ranges that end in mid-air.
-  bool didRepairRange() const { return DidRepairRange; }
-
   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
   /// new interval.
   void clear();
 
   /// getParent - Return the last analyzed interval.
   const LiveInterval &getParent() const { return *CurLI; }
 
   /// isOriginalEndpoint - Return true if the original live range was killed or

llvm/lib/CodeGen/SplitKit.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
 STATISTIC(NumFinished, "Number of splits finished");
 STATISTIC(NumSimple,   "Number of splits that were simple");
 STATISTIC(NumCopies,   "Number of copies inserted for splitting");
 STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
-STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
 
 //===----------------------------------------------------------------------===//
 //                     Last Insert Point Analysis
 //===----------------------------------------------------------------------===//
 
 InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
                                          unsigned BBNum)
     : LIS(lis), LastInsertPoint(BBNum) {}
SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
     : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
       TII(*MF.getSubtarget().getInstrInfo()), IPA(lis, MF.getNumBlockIDs()) {}
 
 void SplitAnalysis::clear() {
   UseSlots.clear();
   UseBlocks.clear();
   ThroughBlocks.clear();
   CurLI = nullptr;
-  DidRepairRange = false;
 }
 
 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
 void SplitAnalysis::analyzeUses() {
   assert(UseSlots.empty() && "Call clear first");
 
   // First get all the defs from the interval values. This provides the correct
   // slots for early clobbers.
void SplitAnalysis::analyzeUses() {
 
   // Remove duplicates, keeping the smaller slot for each instruction.
   // That is what we want for early clobbers.
   UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
                              SlotIndex::isSameInstr),
                  UseSlots.end());
 
   // Compute per-live block info.
-  if (!calcLiveBlockInfo()) {
-    // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
-    // I am looking at you, RegisterCoalescer!
-    DidRepairRange = true;
-    ++NumRepairs;
-    LLVM_DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
-    const_cast<LiveIntervals&>(LIS)
-      .shrinkToUses(const_cast<LiveInterval*>(CurLI));
-    UseBlocks.clear();
-    ThroughBlocks.clear();
-    bool fixed = calcLiveBlockInfo();
-    (void)fixed;
-    assert(fixed && "Couldn't fix broken live interval");
-  }
+  calcLiveBlockInfo();
 
   LLVM_DEBUG(dbgs() << "Analyze counted " << UseSlots.size() << " instrs in "
                     << UseBlocks.size() << " blocks, through "
                     << NumThroughBlocks << " blocks.\n");
 }
 
 /// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
 /// where CurLI is live.
-bool SplitAnalysis::calcLiveBlockInfo() {
+void SplitAnalysis::calcLiveBlockInfo() {
   ThroughBlocks.resize(MF.getNumBlockIDs());
   NumThroughBlocks = NumGapBlocks = 0;
   if (CurLI->empty())
-    return true;
+    return;
 
   LiveInterval::const_iterator LVI = CurLI->begin();
   LiveInterval::const_iterator LVE = CurLI->end();
 
   SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
   UseI = UseSlots.begin();
   UseE = UseSlots.end();
 
while (true) {
     // If the block contains no uses, the range must be live through. At one
     // point, RegisterCoalescer could create dangling ranges that ended
     // mid-block.
     if (UseI == UseE || *UseI >= Stop) {
       ++NumThroughBlocks;
       ThroughBlocks.set(BI.MBB->getNumber());
       // The range shouldn't end mid-block if there are no uses. This shouldn't
       // happen.
-      if (LVI->end < Stop)
-        return false;
+      assert(LVI->end >= Stop && "range ends mid block with no uses");
     } else {
       // This block has uses. Find the first and last uses in the block.
       BI.FirstInstr = *UseI;
       assert(BI.FirstInstr >= Start);
       do ++UseI;
       while (UseI != UseE && *UseI < Stop);
       BI.LastInstr = UseI[-1];
       assert(BI.LastInstr < Stop);
while (true) {
     // Pick the next basic block.
     if (LVI->start < Stop)
       ++MFI;
     else
       MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
   }
 
   assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
-  return true;
 }
 
 unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
   if (cli->empty())
     return 0;
   LiveInterval *li = const_cast<LiveInterval*>(cli);
   LiveInterval::iterator LVI = li->begin();
   LiveInterval::iterator LVE = li->end();