RAGreedy: Keep track of allocated PhysRegs internally

[MatzeB]

Summary

Do not use MachineRegisterInfo::setPhysRegUsed()/isPhysRegUsed()
anymore. This bitset changes function-global state and is set by the
VirtRegRewriter anyway.
Simply use a bitvector private to RAGreedy.

[stoklund]

Instead of maintaining a bitvector in RAGreedy, how about asking LiveRegMatrix? It can tell you if the corresponding LiveIntervalUnion is empty.

[MatzeB]

Good point Jakob; Updated version attached.

[MatzeB]

ping

[stoklund]

lib/CodeGen/RegAllocGreedy.cpp

833

This looks like the guts of LiveRegMatrix are spilling out.

How about moving this code into a LiveRegMatrix::isPhysRegUsed() function instead?

Otherwise, looks good!

lib/CodeGen/RegAllocGreedy.cpp

struct RegInfo {
     // Cascade - Eviction loop prevention. See canEvictInterference().
     unsigned Cascade;
 
     RegInfo() : Stage(RS_New), Cascade(0) {}
   };
 
   IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
 
+  BitVector UsedRegUnits;
+
   LiveRangeStage getStage(const LiveInterval &VirtReg) const {
     return ExtraRegInfo[VirtReg.reg].Stage;
   }
 
   void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
     ExtraRegInfo.resize(MRI->getNumVirtRegs());
     ExtraRegInfo[VirtReg.reg].Stage = Stage;
   }
struct HintInfo {
     /// In case of a physical register Reg == PhysReg.
     unsigned PhysReg;
     HintInfo(BlockFrequency Freq, unsigned Reg, unsigned PhysReg)
         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
   };
   typedef SmallVector<HintInfo, 4> HintsInfo;
   BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned);
   void collectHintInfo(unsigned, HintsInfo &);
+
+  void setRegUsed(unsigned PhysReg);
+  bool isUnusedCSR(unsigned PhysReg) const;
 };
 } // end anonymous namespace
 
 char RAGreedy::ID = 0;
 
 #ifndef NDEBUG
 const char *const RAGreedy::StageName[] = {
     "RS_New",
void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
   ExtraRegInfo.grow(New);
   ExtraRegInfo[New] = ExtraRegInfo[Old];
 }
 
 void RAGreedy::releaseMemory() {
   SpillerInstance.reset();
   ExtraRegInfo.clear();
   GlobalCand.clear();
+  UsedRegUnits.clear();
 }
 
 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
 
 void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
   // Prioritize live ranges by size, assigning larger ranges first.
   // The queue holds (size, reg) pairs.
   const unsigned Size = LI->getSize();
assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
             VirtReg.isSpillable() < Intf->isSpillable()) &&
            "Cannot decrease cascade number, illegal eviction");
     ExtraRegInfo[Intf->reg].Cascade = Cascade;
     ++NumEvicted;
     NewVRegs.push_back(Intf->reg);
   }
 }
 
+/// Returns true if the given \p PhysReg is a callee saved register and has not
+/// been used for allocation yet.
+bool RAGreedy::isUnusedCSR(unsigned PhysReg) const {
+  unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
+  if (CSR == 0)
+    return false;
+
+  for (MCRegUnitIterator Unit(CSR, TRI); Unit.isValid(); ++Unit) {
+    if (UsedRegUnits.test(*Unit))
+      return false;
+  }
+  return true;
+}
+
 /// tryEvict - Try to evict all interferences for a physreg.
 /// @param  VirtReg Currently unassigned virtual register.
 /// @param  Order   Physregs to try.
 /// @return         Physreg to assign VirtReg, or 0.
 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
                             AllocationOrder &Order,
                             SmallVectorImpl<unsigned> &NewVRegs,
                             unsigned CostPerUseLimit) {
unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
   }
 
   Order.rewind();
   while (unsigned PhysReg = Order.next(OrderLimit)) {
     if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
       continue;
     // The first use of a callee-saved register in a function has cost 1.
     // Don't start using a CSR when the CostPerUseLimit is low.
-    if (CostPerUseLimit == 1)
-     if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
-       if (!MRI->isPhysRegUsed(CSR)) {
-         DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
-                      << PrintReg(CSR, TRI) << '\n');
-         continue;
-       }
+    if (CostPerUseLimit == 1 && isUnusedCSR(PhysReg)) {
+            << PrintReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
+            << '\n');
 
     if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
       continue;
 
     // Best so far.
     BestPhys = PhysReg;
 
     // Stop if the hint can be used.

 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
                                             AllocationOrder &Order,
                                             BlockFrequency &BestCost,
                                             unsigned &NumCands,
                                             bool IgnoreCSR) {
   unsigned BestCand = NoCand;
   Order.rewind();
   while (unsigned PhysReg = Order.next()) {
-   if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
-     if (IgnoreCSR && !MRI->isPhysRegUsed(CSR))
-       continue;
+    if (IgnoreCSR && isUnusedCSR(PhysReg))
 
     // Discard bad candidates before we run out of interference cache cursors.
     // This will only affect register classes with a lot of registers (>32).
     if (NumCands == IntfCache.getMaxCursors()) {
       unsigned WorstCount = ~0u;
       unsigned Worst = 0;
       for (unsigned i = 0; i != NumCands; ++i) {
         if (i == BestCand || !GlobalCand[i].PhysReg)
for (unsigned i = Q.interferingVRegs().size(); i; --i) {
         return false;
       }
       RecoloringCandidates.insert(Intf);
     }
   }
   return true;
 }
 
+void RAGreedy::setRegUsed(unsigned PhysReg) {
+  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
+    UsedRegUnits.set(*Unit);
+  }
+}
+
 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
 /// its interferences.
 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
 /// virtual register that was using it. The recoloring process may recursively
 /// use the last chance recoloring. Therefore, when a virtual register has been
 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
 /// be last-chance-recolored again during this recoloring "session".
 /// E.g.,
for (SmallLISet::iterator It = RecoloringCandidates.begin(),
       // unset the related struct.
       Matrix->unassign(**It);
     }
 
     // Do as if VirtReg was assigned to PhysReg so that the underlying
     // recoloring has the right information about the interferes and
     // available colors.
     Matrix->assign(VirtReg, PhysReg);
+    setRegUsed(PhysReg);
 
     // Save the current recoloring state.
     // If we cannot recolor all the interferences, we will have to start again
     // at this point for the next physical register.
     SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
     if (tryRecoloringCandidates(RecoloringQueue, NewVRegs, FixedRegisters,
                                 Depth)) {
       // Do not mess up with the global assignment process.
while (unsigned PhysReg = Order.next()) {
     Matrix->unassign(VirtReg);
 
     for (SmallLISet::iterator It = RecoloringCandidates.begin(),
                               EndIt = RecoloringCandidates.end();
          It != EndIt; ++It) {
       unsigned ItVirtReg = (*It)->reg;
       if (VRM->hasPhys(ItVirtReg))
         Matrix->unassign(**It);
-      Matrix->assign(**It, VirtRegToPhysReg[ItVirtReg]);
+      unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
+      Matrix->assign(**It, ItPhysReg);
+      setRegUsed(ItPhysReg);
     }
   }
 
   // Last chance recoloring did not worked either, give up.
   return ~0u;
 }
 
 /// tryRecoloringCandidates - Try to assign a new color to every register
while (!RecoloringQueue.empty()) {
     DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
     unsigned PhysReg;
     PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
     if (PhysReg == ~0u || !PhysReg)
       return false;
     DEBUG(dbgs() << "Recoloring of " << *LI
                  << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n');
     Matrix->assign(*LI, PhysReg);
+    setRegUsed(PhysReg);
     FixedRegisters.insert(LI->reg);
   }
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 //                            Main Entry Point
 //===----------------------------------------------------------------------===//
else if (CutOffEncountered == CO_Interf)
       Ctx.emitError("register allocation failed: maximum interference for "
                     "recoloring reached. Use -fexhaustive-register-search "
                     "to skip cutoffs");
     else if (CutOffEncountered == (CO_Depth | CO_Interf))
       Ctx.emitError("register allocation failed: maximum interference and "
                     "depth for recoloring reached. Use "
                     "-fexhaustive-register-search to skip cutoffs");
   }
+  if (Reg != 0 && Reg != ~0U)
+    setRegUsed(Reg);
   return Reg;
 }
 
 /// Using a CSR for the first time has a cost because it causes push|pop
 /// to be added to prologue|epilogue. Splitting a cold section of the live
 /// range can have lower cost than using the CSR for the first time;
 /// Spilling a live range in the cold path can have lower cost than using
 /// the CSR for the first time. Returns the physical register if we decide
if (CurrPhys != PhysReg) {
       }
       // At this point, the cost is either cheaper or equal. If it is
       // equal, we consider this is profitable because it may expose
       // more recoloring opportunities.
       DEBUG(dbgs() << "=> Profitable.\n");
       // Recolor the live-range.
       Matrix->unassign(LI);
       Matrix->assign(LI, PhysReg);
+      setRegUsed(PhysReg);
     }
     // Push all copy-related live-ranges to keep reconciling the broken
     // hints.
     for (const HintInfo &HI : Info) {
       if (Visited.insert(HI.Reg).second)
         RecoloringCandidates.push_back(HI.Reg);
     }
   } while (!RecoloringCandidates.empty());

 unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
                                      SmallVectorImpl<unsigned> &NewVRegs,
                                      SmallVirtRegSet &FixedRegisters,
                                      unsigned Depth) {
   unsigned CostPerUseLimit = ~0u;
   // First try assigning a free register.
   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo);
   if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
-    // We check other options if we are using a CSR for the first time.
-    bool CSRFirstUse = false;
-    if (unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg))
-      if (!MRI->isPhysRegUsed(CSR))
-        CSRFirstUse = true;
-
     // When NewVRegs is not empty, we may have made decisions such as evicting
     // a virtual register, go with the earlier decisions and use the physical
     // register.
-    if (CSRCost.getFrequency() && CSRFirstUse && NewVRegs.empty()) {
+    if (CSRCost.getFrequency() && isUnusedCSR(PhysReg) && NewVRegs.empty()) {
       unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
                                               CostPerUseLimit, NewVRegs);
       if (CSRReg || !NewVRegs.empty())
         // Return now if we decide to use a CSR or create new vregs due to
         // pre-splitting.
         return CSRReg;
     } else
       return PhysReg;
bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
                << "********** Function: " << mf.getName() << '\n');
 
   MF = &mf;
   TRI = MF->getSubtarget().getRegisterInfo();
   TII = MF->getSubtarget().getInstrInfo();
   RCI.runOnMachineFunction(mf);
 
+  UsedRegUnits.resize(TRI->getNumRegUnits());
+
   EnableLocalReassign = EnableLocalReassignment ||
                         MF->getSubtarget().enableRALocalReassignment(
                             MF->getTarget().getOptLevel());
 
   if (VerifyEnabled)
     MF->verify(this, "Before greedy register allocator");
 
   RegAllocBase::init(getAnalysis<VirtRegMap>(),