Add LiveRegMatrix::checkInterferenceWithRange

[MatzeB]

Summary

Part of an experiment to spill to vector registers. Uploading for inspiration, this is not finished!

llvm/include/llvm/CodeGen/LiveIntervals.h

public:
     void releaseMemory() override;
 
     /// Pass entry point; Calculates LiveIntervals.
     bool runOnMachineFunction(MachineFunction&) override;
 
     /// Implement the dump method.
     void print(raw_ostream &O, const Module* = nullptr) const override;
 
-    /// If LI is confined to a single basic block, return a pointer to that
-    /// block.  If LI is live in to or out of any block, return NULL.
-    MachineBasicBlock *intervalIsInOneMBB(const LiveInterval &LI) const;
+    /// If LR is confined to a single basic block, return a pointer to that
+    /// block.  If LR is live in to or out of any block, return NULL.
+    MachineBasicBlock *intervalIsInOneMBB(const LiveRange &LR) const;
 
     /// Returns true if VNI is killed by any PHI-def values in LI.
     /// This may conservatively return true to avoid expensive computations.
     bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const;
 
     /// Add kill flags to any instruction that kills a virtual register.
     void addKillFlags(const VirtRegMap*);
 
public:
     }
 
     /// Test if \p LI is live across any register mask instructions, and
     /// compute a bit mask of physical registers that are not clobbered by any
     /// of them.
     ///
     /// Returns false if \p LI doesn't cross any register mask instructions. In
     /// that case, the bit vector is not filled in.
-    bool checkRegMaskInterference(LiveInterval &LI,
+    bool checkRegMaskInterference(const LiveRange &LR, Register VirtReg,
                                   BitVector &UsableRegs);
 
     // Register unit functions.
     //
     // Fixed interference occurs when MachineInstrs use physregs directly
     // instead of virtual registers. This typically happens when passing
     // arguments to a function call, or when instructions require operands in
     // fixed registers.

llvm/include/llvm/CodeGen/LiveRegMatrix.h

public:
 
   /// Check for interference in the segment [Start, End) that may prevent
   /// assignment to PhysReg. If this function returns true, there is
   /// interference in the segment [Start, End) of some other interval already
   /// assigned to PhysReg. If this function returns false, PhysReg is free at
   /// the segment [Start, End).
   bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg);
 
+  bool checkInterferenceWithRange(const LiveRange& Range, MCRegister PhysReg);
+
   /// Assign VirtReg to PhysReg.
   /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
   /// update VirtRegMap. The live range is expected to be available in PhysReg.
   void assign(LiveInterval &VirtReg, MCRegister PhysReg);
 
   /// Unassign VirtReg from its PhysReg.
   /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
   /// the assignment and updates VirtRegMap accordingly.
   void unassign(LiveInterval &VirtReg);
 
   /// Returns true if the given \p PhysReg has any live intervals assigned.
   bool isPhysRegUsed(MCRegister PhysReg) const;
 
   //===--------------------------------------------------------------------===//
   // Low-level interface.
   //===--------------------------------------------------------------------===//
   //
   // Provide access to the underlying LiveIntervalUnions.
   //
 
   /// Check for regmask interference only.
-  /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
-  /// If PhysReg is null, check if VirtReg crosses any regmask operands.
-  bool checkRegMaskInterference(LiveInterval &VirtReg,
+  /// Return true if live range LR crosses a regmask operand that clobbers
+  /// PhysReg.  If PhysReg is NoRegister, check if LR crosses any regmask
+  /// operands.
+  bool checkRegMaskInterference(const LiveRange& LR, Register VirtReg,
                                 MCRegister PhysReg = MCRegister::NoRegister);
 
   /// Check for regunit interference only.
   /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
   /// register units.
   bool checkRegUnitInterference(LiveInterval &VirtReg, MCRegister PhysReg);
 
   /// Query a line of the assigned virtual register matrix directly.

llvm/lib/CodeGen/LiveIntervals.cpp

for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
       continue;
 CancelKill:
       MI->clearRegisterKills(Reg, nullptr);
     }
   }
 }
 
 MachineBasicBlock*
-LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
+LiveIntervals::intervalIsInOneMBB(const LiveRange &LR) const {
   // A local live range must be fully contained inside the block, meaning it is
   // defined and killed at instructions, not at block boundaries. It is not
   // live in or out of any block.
   //
   // It is technically possible to have a PHI-defined live range identical to a
   // single block, but we are going to return false in that case.
 
-  SlotIndex Start = LI.beginIndex();
+  SlotIndex Start = LR.beginIndex();
   if (Start.isBlock())
     return nullptr;
 
-  SlotIndex Stop = LI.endIndex();
+  SlotIndex Stop = LR.endIndex();
   if (Stop.isBlock())
     return nullptr;
 
   // getMBBFromIndex doesn't need to search the MBB table when both indexes
   // belong to proper instructions.
   MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
   MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
   return MBB1 == MBB2 ? MBB1 : nullptr;
LiveIntervals::addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst) {
 
   return S;
 }
 
 //===----------------------------------------------------------------------===//
 //                          Register mask functions
 //===----------------------------------------------------------------------===//
 
-bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
+bool LiveIntervals::checkRegMaskInterference(const LiveRange &LR, Register VirtReg,
                                              BitVector &UsableRegs) {
-  if (LI.empty())
+  if (LR.empty())
     return false;
-  LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
+  LiveRange::const_iterator LiveI = LR.begin(), LiveE = LR.end();
 
   // Use a smaller arrays for local live ranges.
   ArrayRef<SlotIndex> Slots;
   ArrayRef<const uint32_t*> Bits;
-  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
+  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LR)) {
     Slots = getRegMaskSlotsInBlock(MBB->getNumber());
     Bits = getRegMaskBitsInBlock(MBB->getNumber());
   } else {
     Slots = getRegMaskSlots();
     Bits = getRegMaskBits();
   }
 
-  // We are going to enumerate all the register mask slots contained in LI.
+  // We are going to enumerate all the register mask slots contained in LR.
   // Start with a binary search of RegMaskSlots to find a starting point.
   ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);
   ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
 
-  // No slots in range, LI begins after the last call.
+  // No slots in range, LR begins after the last call.
   if (SlotI == SlotE)
     return false;
 
   bool Found = false;
   while (true) {
     assert(*SlotI >= LiveI->start);
     // Loop over all slots overlapping this segment.
     while (*SlotI < LiveI->end) {
-      // *SlotI overlaps LI. Collect mask bits.
+      // *SlotI overlaps LR. Collect mask bits.
       if (!Found) {
         // This is the first overlap. Initialize UsableRegs to all ones.
         UsableRegs.clear();
         UsableRegs.resize(TRI->getNumRegs(), true);
         Found = true;
       }
       // Remove usable registers clobbered by this mask.
       UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
       if (++SlotI == SlotE)
         return Found;
     }
-    // *SlotI is beyond the current LI segment.
-    LiveI = LI.advanceTo(LiveI, *SlotI);
+    // *SlotI is beyond the current LR segment.
+    LiveI = LR.advanceTo(LiveI, *SlotI);
     if (LiveI == LiveE)
       return Found;
     // Advance SlotI until it overlaps.
     while (*SlotI < LiveI->start)
       if (++SlotI == SlotE)
         return Found;
   }
 }

llvm/lib/CodeGen/LiveRegMatrix.cpp

 bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {
   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     if (!Matrix[*Unit].empty())
       return true;
   }
   return false;
 }
 
-bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
+bool LiveRegMatrix::checkRegMaskInterference(const LiveRange &LR,
+                                             Register VirtReg,
                                              MCRegister PhysReg) {
   // Check if the cached information is valid.
   // The same BitVector can be reused for all PhysRegs.
   // We could cache multiple VirtRegs if it becomes necessary.
-  if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) {
-    RegMaskVirtReg = VirtReg.reg();
+  if (VirtReg == MCRegister::NoRegister || RegMaskVirtReg != VirtReg ||
+      RegMaskTag != UserTag) {
+    RegMaskVirtReg = VirtReg;
     RegMaskTag = UserTag;
     RegMaskUsable.clear();
-    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
+    LIS->checkRegMaskInterference(LR, VirtReg, RegMaskUsable);
   }
 
   // The BitVector is indexed by PhysReg, not register unit.
   // Regmask interference is more fine grained than regunits.
   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
 }
 

 }
 
 LiveRegMatrix::InterferenceKind
 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, MCRegister PhysReg) {
   if (VirtReg.empty())
     return IK_Free;
 
   // Regmask interference is the fastest check.
-  if (checkRegMaskInterference(VirtReg, PhysReg))
+  if (checkRegMaskInterference(VirtReg, VirtReg.reg(), PhysReg))
     return IK_RegMask;
 
   // Check for fixed interference.
   if (checkRegUnitInterference(VirtReg, PhysReg))
     return IK_RegUnit;
 
   // Check the matrix for virtual register interference.
   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
   // Check for interference with that segment
   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
     if (query(LR, *Units).checkInterference())
       return true;
   }
   return false;
 }
 
+bool LiveRegMatrix::checkInterferenceWithRange(const LiveRange& LR, MCRegister PhysReg) {
+  if (LR.empty())
+    return false;
+
+  // Regmask interference is the fastest check.
+  if (checkRegMaskInterference(LR, MCRegister::NoRegister, PhysReg))
+    return true;
+
+  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
+    // Check for fixed interference.
+    const LiveRange &UnitRange = LIS->getRegUnit(*Units);
+    if (LR.overlaps(UnitRange))
+      return true;
+    // Check for interference with current assignments.
+    if (query(LR, *Units).checkInterference())
+      return true;
+  }
+  return false;
+}
+
 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
   LiveInterval *VRegInterval = nullptr;
   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
     if ((VRegInterval = Matrix[*Unit].getOneVReg()))
       return VRegInterval->reg();
   }
 
   return MCRegister::NoRegister;
 }

llvm/lib/CodeGen/RegAllocGreedy.cpp

LLVM_DEBUG({
     for (const auto &Use : Uses)
       dbgs() << ' ' << Use;
     dbgs() << '\n';
   });
 
   // If VirtReg is live across any register mask operands, compute a list of
   // gaps with register masks.
   SmallVector<unsigned, 8> RegMaskGaps;
-  if (Matrix->checkRegMaskInterference(VirtReg)) {
+  if (Matrix->checkRegMaskInterference(VirtReg, VirtReg.reg())) {
     // Get regmask slots for the whole block.
     ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
     LLVM_DEBUG(dbgs() << RMS.size() << " regmasks in block:");
     // Constrain to VirtReg's live range.
     unsigned RI =
         llvm::lower_bound(RMS, Uses.front().getRegSlot()) - RMS.begin();
     unsigned RE = RMS.size();
     for (unsigned I = 0; I != NumGaps && RI != RE; ++I) {
unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
 
   for (MCPhysReg PhysReg : Order) {
     assert(PhysReg);
     // Keep track of the largest spill weight that would need to be evicted in
     // order to make use of PhysReg between UseSlots[I] and UseSlots[I + 1].
     calcGapWeights(PhysReg, GapWeight);
 
     // Remove any gaps with regmask clobbers.
-    if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
+    if (Matrix->checkRegMaskInterference(VirtReg, VirtReg.reg(), PhysReg))
       for (unsigned I = 0, E = RegMaskGaps.size(); I != E; ++I)
         GapWeight[RegMaskGaps[I]] = huge_valf;
 
     // Try to find the best sequence of gaps to close.
     // The new spill weight must be larger than any gap interference.
 
     // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
     unsigned SplitBefore = 0, SplitAfter = 1;

llvm/lib/CodeGen/RegAllocPBQP.cpp

if (VRegLI.empty()) {
       VRegsToAlloc.erase(VRegLI.reg());
       continue;
     }
 
     const TargetRegisterClass *TRC = MRI.getRegClass(VReg);
 
     // Record any overlaps with regmask operands.
     BitVector RegMaskOverlaps;
-    LIS.checkRegMaskInterference(VRegLI, RegMaskOverlaps);
+    LIS.checkRegMaskInterference(VRegLI, VRegLI.reg(), RegMaskOverlaps);
 
     // Compute an initial allowed set for the current vreg.
     std::vector<MCRegister> VRegAllowed;
     ArrayRef<MCPhysReg> RawPRegOrder = TRC->getRawAllocationOrder(MF);
     for (unsigned I = 0; I != RawPRegOrder.size(); ++I) {
       MCRegister PReg(RawPRegOrder[I]);
       if (MRI.isReserved(PReg))
         continue;

llvm/lib/CodeGen/RegisterCoalescer.cpp

for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
         LLVM_DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(*UI, TRI)
                           << '\n');
         return false;
       }
     }
 
     // We must also check for overlaps with regmask clobbers.
     BitVector RegMaskUsable;
-    if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&
+    if (LIS->checkRegMaskInterference(RHS, RHS.reg(), RegMaskUsable) &&
         !RegMaskUsable.test(DstReg)) {
       LLVM_DEBUG(dbgs() << "\t\tRegMask interference\n");
       return false;
     }
   }
 
   // Skip any value computations, we are not adding new values to the
   // reserved register.  Also skip merging the live ranges, the reserved