[RegisterCoalescer] Add verification method to check LiveInterval Segments

[dstuttard]

Summary

I've been looking at SubRange Join asserts and this function is useful to help
pinpoint problems.

I've added it in this case as an optional post RegisterCoalescer verification
check that is controlled with the -verify-live-intervals command line flag.

In reality, this check is better done just after a call to joinCopy as this will
pinpoint the precise transformation that results in illegal Segments, but I
didn't want to add an additional check for a CL flag in the core of the pass.
If you are debugging this type of problem it is easier to manually insert the
call to the check where appropriate.

The verification pass determines if there are any Segments that contain a start
or end SlotIndex that no longer exist.
These types of issue are more common for SubRanges and most of the debugging
I've done has been in this area.

[dstuttard]

I've got a couple of new SubRange join fixes that I'm about to upload for review. This routine was useful in tracking those down so I thought it would be useful to add as a generic aid for future problems.

[dstuttard]

Removed a blank line causing unnecessary differences

[dstuttard]

Removing debug code

[qcolombet]

Hi,

We already checks the liveinterval in the MachineVerifier (see MachineVerifier::checkLiveness). Could we share the logic between this one and the one in the MachineVerifier?

At the very least, the MachineVerifier should call this method.

Cheers,
-Quentin

[MatzeB]

In D40297#936084, @qcolombet wrote:

Hi,

We already checks the liveinterval in the MachineVerifier (see MachineVerifier::checkLiveness). Could we share the logic between this one and the one in the MachineVerifier?

At the very least, the MachineVerifier should call this method.

Cheers,
-Quentin

+1 We should try to avoid duplicating all the code already present in the MachineVerifier. I'd rather see us starting to refactor the MachineVerifier code to be useful outside of the MachineVerifier.

Glancing at the code, would it be possible to extract some MachineVerifierBase class from MachineVerifier with foundErrors, the various reportXXX functions and verifyLiveIntervals()?

[MatzeB]

lib/CodeGen/RegisterCoalescer.cpp

98–101

Is there anything wrong with the existing -verify-coalescing switch that runs the machine verifier after coalescing, shouldn't that catch the same sort of errors?

[dstuttard]

The intent of this code is really to allow anyone doing debug to insert a check anywhere in the code. In particular, for the problems I was looking at I needed to check the live intervals after each change made in order to pinpoint where an error was being introduced. As implemented here (with the check after coalescing) it looks redundant, so having that extra check is probably useless.
Running a verification phase after coalescing is sometimes too late, and indeed may well have asserted before this point.

I agree that duplicating code isn't desirable, so the suggestion of re-factoring the existing MachineVerifier code to allow invocations in this way is probably better. I'll take a look.

include/llvm/CodeGen/LiveIntervalAnalysis.h

public:
     void splitSeparateComponents(LiveInterval &LI,
                                  SmallVectorImpl<LiveInterval*> &SplitLIs);
 
     /// For live interval \p LI with correct SubRanges construct matching
     /// information for the main live range. Expects the main live range to not
     /// have any segments or value numbers.
     void constructMainRangeFromSubranges(LiveInterval &LI);
 
+    /// Simple check to verify that segments/SlotIndices are valid in
+    /// LiveIntervals including SubRanges
+    bool verifySegments(void) const;
+
   private:
     /// Compute live intervals for all virtual registers.
     void computeVirtRegs();
 
     /// Compute RegMaskSlots and RegMaskBits.
     void computeRegMasks();
 
     /// Walk the values in \p LI and check for dead values:

lib/CodeGen/LiveIntervalAnalysis.cpp

void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
   ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
 }
 
 void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
   assert(LRCalc && "LRCalc not initialized.");
   LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
   LRCalc->constructMainRangeFromSubranges(LI);
 }
+
+bool LiveIntervals::verifySegments(void) const {
+  // Simple verification that ensures that all the Intervals and SubRanges refer
+  // to valid slots.
+  // This is intended to be used for testing purposes - usually after
+  // encountering code that provokes a SubRange join assertion
+
+  bool Result = true;
+
+  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+    if (hasInterval(Reg)) {
+      const LiveInterval &Interval = getInterval(Reg);
+      for (const LiveInterval::Segment &S : Interval.segments) {
+        MachineInstr *MI = nullptr;
+        if (!S.start.isBlock()) {
+          MI = getInstructionFromIndex(S.start);
+          if (!MI) {
+            DEBUG(dbgs() << "verifySegments " << Interval << " : bad segment start = " << S << "\n");
+            Result = false;
+          }
+        }
+        if (!S.end.isBlock()) {
+          MI = getInstructionFromIndex(S.end);
+          if (!MI) {
+            DEBUG(dbgs() << "verifySegments " << Interval << " : bad segment end = " << S << "\n");
+            Result = false;
+          }
+        }
+      }
+
+      // Check SubRanges
+      for (const LiveInterval::SubRange &SR : Interval.subranges()) {
+        for (const LiveInterval::Segment &S : SR.segments) {
+          MachineInstr *MI = nullptr;
+          if (!S.start.isBlock()) {
+            MI = getInstructionFromIndex(S.start);
+            if (!MI) {
+              DEBUG(dbgs() << "verifySegments " << Interval << " : SubRange : " << SR << " : bad segment start = " << S << "\n");
+              Result = false;
+            }
+          }
+          if (!S.end.isBlock()) {
+            MI = getInstructionFromIndex(S.end);
+            if (!MI) {
+              DEBUG(dbgs() << "verifySegments " << Interval << " : SubRange : " << SR << " : bad segment end = " << S << "\n");
+              Result = false;
+            }
+          }
+        }
+      }
+    }
+  }
+  return Result;
+}
+

lib/CodeGen/RegisterCoalescer.cpp

EnableGlobalCopies("join-globalcopies",
   cl::desc("Coalesce copies that span blocks (default=subtarget)"),
   cl::init(cl::BOU_UNSET), cl::Hidden);
 
 static cl::opt<bool>
 VerifyCoalescing("verify-coalescing",
          cl::desc("Verify machine instrs before and after register coalescing"),
          cl::Hidden);
 
+static cl::opt<bool>
+VerifyLiveIntervals("verify-live-intervals",
+         cl::desc("Verify LiveIntervals by inspecting all Segments for invalid slot indices"),
+         cl::Hidden);
+
 namespace {
 
   class RegisterCoalescer : public MachineFunctionPass,
                             private LiveRangeEdit::Delegate {
     MachineFunction* MF;
     MachineRegisterInfo* MRI;
     const TargetRegisterInfo* TRI;
     const TargetInstrInfo* TII;
#ifndef NDEBUG
             assert((S.LaneMask & ~MaxMask).none());
           }
 #endif
         }
       }
     }
   }
 
+  // Verify that the Segments in the LiveIntervals are still valid
+  // This check looks for Segments within Intervals that start or end with
+  // invalid slot indices
+  // It is often more helpful for debug to insert this check after each joinCopy
+  // to pinpoint the precise cause of the error
+  if (VerifyLiveIntervals)
+    // Check that LiveIntervals are still valid after joinCopy
+    assert(LIS->verifySegments() && "joinCopy has resulted in invalid Segments in liveIntervals");
+
   DEBUG(dump());
   if (VerifyCoalescing)
     MF->verify(this, "After register coalescing");
   return true;
 }
 
 void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
    LIS->print(O, m);
 }