Refactor live reg tracking for DAG scheduling.

[chfast]

Summary

Some time ago I had to fix some issues around live reg tracking in DAG scheduling. The logic there is quite hard to follow.
After that I tried to extract the logic from the scheduler itself. I'm not sure it is anything better what it was.

If the change is worth anything let me know. I can work a bit more on that.

I'm also considering replacing the array with a map. It contains mostly nulls.

[chfast]

Ping.

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

static cl::opt<int> MaxReorderWindow(
   cl::desc("Number of instructions to allow ahead of the critical path "
            "in sched=list-ilp"));
 
 static cl::opt<unsigned> AvgIPC(
   "sched-avg-ipc", cl::Hidden, cl::init(1),
   cl::desc("Average inst/cycle whan no target itinerary exists."));
 
 namespace {
+
+class LiveRegManager {
+  /// LiveRegDefs - A set of physical registers and their definition
+  /// that are "live". These nodes must be scheduled before any other nodes that
+  /// modifies the registers can be scheduled.
+  unsigned NumLiveRegs = 0;
+  std::vector<SUnit*> Defs;
+  std::vector<SUnit*> Gens;
+
+public:
+  LiveRegManager() = default;
+  LiveRegManager(const LiveRegManager &) = delete;
+  LiveRegManager& operator=(const LiveRegManager &) = delete;
+
+  void init(unsigned NumRegs) {
+    // Allocate slots for each physical register, plus one for a special register
+    // to track the virtual resource of a calling sequence.
+    Defs.resize(NumRegs + 1);
+    Gens.resize(NumRegs + 1);
+  }
+
+  SUnit* getDef(unsigned Reg) const {
+    assert((!Defs[Reg] || NumLiveRegs) && "Invalid number of live regs");
+    return Defs[Reg];
+  }
+
+  void setDef(unsigned Reg, SUnit* SU) {
+    assert(SU && "Invalid Def");
+    Defs[Reg] = SU;
+  }
+
+  SUnit* getGen(unsigned Reg) const {
+    assert((!Gens[Reg] || NumLiveRegs) && "Invalid number of live regs");
+    assert((!Gens[Reg] || Defs[Reg]) && "Def missing");
+    return Gens[Reg];
+  }
+
+  void setGen(unsigned Reg, SUnit* SU) {
+    assert(SU && "Invalid Gen");
+    assert(Defs[Reg] && "Def missing");
+    Gens[Reg] = SU;
+  }
+
+  void clear(unsigned Reg) {
+    assert(Reg < Defs.size() - 1 && "Invalid live reg number");
+    assert(NumLiveRegs > 0 && Defs[Reg] && Gens[Reg] && "Live reg not set");
+    --NumLiveRegs;
+    Defs[Reg] = nullptr;
+    Gens[Reg] = nullptr;
+  }
+
+  SUnit* getCallResourceDef() const { return Defs.back(); }
+  SUnit* getCallResourceGen() const { return Gens.back(); }
+  void setCallResource(SUnit* Def, SUnit* Gen) {
+    ++NumLiveRegs;
+    Defs.back() = Def;
+    Gens.back() = Gen;
+  }
+
+  void clearCallResource() {
+    assert(NumLiveRegs > 0 && Defs.back() && Gens.back() && "Call resource not set");
+    --NumLiveRegs;
+    Defs.back() = nullptr;
+    Gens.back() = nullptr;
+  }
+
+  bool empty() const { return NumLiveRegs == 0; }
+
+  void incCounter() { ++NumLiveRegs; }
+
+  const std::vector<SUnit*>& getDefs() const { return Defs; }
+};
+
+
 //===----------------------------------------------------------------------===//
 /// ScheduleDAGRRList - The actual register reduction list scheduler
 /// implementation.  This supports both top-down and bottom-up scheduling.
 ///
 class ScheduleDAGRRList : public ScheduleDAGSDNodes {
 private:
   /// NeedLatency - True if the scheduler will make use of latency information.
   ///
private:
   ScheduleHazardRecognizer *HazardRec;
 
   /// CurCycle - The current scheduler state corresponds to this cycle.
   unsigned CurCycle;
 
   /// MinAvailableCycle - Cycle of the soonest available instruction.
   unsigned MinAvailableCycle;
 
+  LiveRegManager LiveRegs;
+
   /// IssueCount - Count instructions issued in this cycle
   /// Currently valid only for bottom-up scheduling.
   unsigned IssueCount;
 
-  /// LiveRegDefs - A set of physical registers and their definition
-  /// that are "live". These nodes must be scheduled before any other nodes that
-  /// modifies the registers can be scheduled.
-  unsigned NumLiveRegs;
-  std::vector<SUnit*> LiveRegDefs;
-  std::vector<SUnit*> LiveRegGens;
-
   // Collect interferences between physical register use/defs.
   // Each interference is an SUnit and set of physical registers.
   SmallVector<SUnit*, 4> Interferences;
   typedef DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMapT;
   LRegsMapT LRegsMap;
 
   /// Topo - A topological ordering for SUnits which permits fast IsReachable
   /// and similar queries.

 void ScheduleDAGRRList::Schedule() {
   DEBUG(dbgs()
         << "********** List Scheduling BB#" << BB->getNumber()
         << " '" << BB->getName() << "' **********\n");
 
   CurCycle = 0;
   IssueCount = 0;
   MinAvailableCycle = DisableSchedCycles ? 0 : UINT_MAX;
-  NumLiveRegs = 0;
-  // Allocate slots for each physical register, plus one for a special register
-  // to track the virtual resource of a calling sequence.
-  LiveRegDefs.resize(TRI->getNumRegs() + 1, nullptr);
-  LiveRegGens.resize(TRI->getNumRegs() + 1, nullptr);
+  LiveRegs.init(TRI->getNumRegs());
   CallSeqEndForStart.clear();
   assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
 
   // Build the scheduling graph.
   BuildSchedGraph(nullptr);
 
   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
           SUnits[su].dumpAll(this));
void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
     ReleasePred(SU, &*I);
     if (I->isAssignedRegDep()) {
       // This is a physical register dependency and it's impossible or
       // expensive to copy the register. Make sure nothing that can
       // clobber the register is scheduled between the predecessor and
       // this node.
-      SUnit *RegDef = LiveRegDefs[I->getReg()]; (void)RegDef;
+      SUnit *RegDef = LiveRegs.getDef(I->getReg()); (void)RegDef;
       assert((!RegDef || RegDef == SU || RegDef == I->getSUnit()) &&
              "interference on register dependence");
-      LiveRegDefs[I->getReg()] = I->getSUnit();
-      if (!LiveRegGens[I->getReg()]) {
-        ++NumLiveRegs;
-        LiveRegGens[I->getReg()] = SU;
+      LiveRegs.setDef(I->getReg(), I->getSUnit());
+      if (!LiveRegs.getGen(I->getReg())) {
+        LiveRegs.incCounter();
+        LiveRegs.setGen(I->getReg(), SU);
       }
     }
   }
 
   // If we're scheduling a lowered CALLSEQ_END, find the corresponding
   // CALLSEQ_BEGIN. Inject an artificial physical register dependence between
   // these nodes, to prevent other calls from being interscheduled with them.
-  unsigned CallResource = TRI->getNumRegs();
-  if (!LiveRegDefs[CallResource])
+  if (!LiveRegs.getCallResourceDef())
     for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())
       if (Node->isMachineOpcode() &&
           Node->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
         unsigned NestLevel = 0;
         unsigned MaxNest = 0;
         SDNode *N = FindCallSeqStart(Node, NestLevel, MaxNest, TII);
 
         SUnit *Def = &SUnits[N->getNodeId()];
         CallSeqEndForStart[Def] = SU;
 
-        ++NumLiveRegs;
-        LiveRegDefs[CallResource] = Def;
-        LiveRegGens[CallResource] = SU;
+        LiveRegs.setCallResource(Def, SU);
         break;
       }
 }
 
 /// Check to see if any of the pending instructions are ready to issue.  If
 /// so, add them to the available queue.
 void ScheduleDAGRRList::ReleasePending() {
   if (DisableSchedCycles) {
#endif
   // Update liveness of predecessors before successors to avoid treating a
   // two-address node as a live range def.
   ReleasePredecessors(SU);
 
   // Release all the implicit physical register defs that are live.
   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
        I != E; ++I) {
     // LiveRegDegs[I->getReg()] != SU when SU is a two-address node.
-    if (I->isAssignedRegDep() && LiveRegDefs[I->getReg()] == SU) {
-      assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-      --NumLiveRegs;
-      LiveRegDefs[I->getReg()] = nullptr;
-      LiveRegGens[I->getReg()] = nullptr;
+    if (I->isAssignedRegDep() && LiveRegs.getDef(I->getReg()) == SU) {
+      LiveRegs.clear(I->getReg());
       releaseInterferences(I->getReg());
     }
   }
   // Release the special call resource dependence, if this is the beginning
   // of a call.
-  unsigned CallResource = TRI->getNumRegs();
-  if (LiveRegDefs[CallResource] == SU)
+  if (LiveRegs.getCallResourceDef() == SU)
     for (const SDNode *SUNode = SU->getNode(); SUNode;
          SUNode = SUNode->getGluedNode()) {
       if (SUNode->isMachineOpcode() &&
           SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameSetupOpcode()) {
-        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-        --NumLiveRegs;
-        LiveRegDefs[CallResource] = nullptr;
-        LiveRegGens[CallResource] = nullptr;
+        LiveRegs.clearCallResource();
+        unsigned CallResource = TRI->getNumRegs();
         releaseInterferences(CallResource);
       }
     }
 
   resetVRegCycle(SU);
 
   SU->isScheduled = true;
 

 /// its predecessor states to reflect the change.
 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
   DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
   DEBUG(SU->dump(this));
 
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
     CapturePred(&*I);
-    if (I->isAssignedRegDep() && SU == LiveRegGens[I->getReg()]){
-      assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-      assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
+    if (I->isAssignedRegDep() && LiveRegs.getGen(I->getReg()) == SU) {
+      assert(LiveRegs.getDef(I->getReg()) == I->getSUnit() &&
              "Physical register dependency violated?");
-      --NumLiveRegs;
-      LiveRegDefs[I->getReg()] = nullptr;
-      LiveRegGens[I->getReg()] = nullptr;
+      LiveRegs.clear(I->getReg());
       releaseInterferences(I->getReg());
     }
   }
 
   // Reclaim the special call resource dependence, if this is the beginning
   // of a call.
   unsigned CallResource = TRI->getNumRegs();
   for (const SDNode *SUNode = SU->getNode(); SUNode;
        SUNode = SUNode->getGluedNode()) {
     if (SUNode->isMachineOpcode() &&
         SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameSetupOpcode()) {
-      ++NumLiveRegs;
-      LiveRegDefs[CallResource] = SU;
-      LiveRegGens[CallResource] = CallSeqEndForStart[SU];
+      LiveRegs.setCallResource(SU, CallSeqEndForStart[SU]);
     }
   }
 
   // Release the special call resource dependence, if this is the end
   // of a call.
-  if (LiveRegGens[CallResource] == SU)
+  if (LiveRegs.getCallResourceGen() == SU)
     for (const SDNode *SUNode = SU->getNode(); SUNode;
          SUNode = SUNode->getGluedNode()) {
       if (SUNode->isMachineOpcode() &&
           SUNode->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
-        assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
-        --NumLiveRegs;
-        LiveRegDefs[CallResource] = nullptr;
-        LiveRegGens[CallResource] = nullptr;
+        LiveRegs.clearCallResource();
         releaseInterferences(CallResource);
       }
     }
 
   for (auto &Succ : SU->Succs) {
     if (Succ.isAssignedRegDep()) {
       auto Reg = Succ.getReg();
-      if (!LiveRegDefs[Reg])
-        ++NumLiveRegs;
+      if (!LiveRegs.getDef(Reg))
+        LiveRegs.incCounter();
       // This becomes the nearest def. Note that an earlier def may still be
       // pending if this is a two-address node.
-      LiveRegDefs[Reg] = SU;
+      LiveRegs.setDef(Reg, SU);
 
       // Update LiveRegGen only if was empty before this unscheduling.
       // This is to avoid incorrect updating LiveRegGen set in previous run.
-      if (!LiveRegGens[Reg]) {
+      if (!LiveRegs.getGen(Reg)) {
         // Find the successor with the lowest height.
-        LiveRegGens[Reg] = Succ.getSUnit();
+        auto Gen = Succ.getSUnit();
         for (auto &Succ2 : SU->Succs) {
           if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
-              Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
-            LiveRegGens[Reg] = Succ2.getSUnit();
+              Succ2.getSUnit()->getHeight() < Gen->getHeight())
+            Gen = Succ2.getSUnit();
         }
+        LiveRegs.setGen(Reg, Gen);
       }
     }
   }
   if (SU->getHeight() < MinAvailableCycle)
     MinAvailableCycle = SU->getHeight();
 
   SU->setHeightDirty();
   SU->isScheduled = false;
if (N->getOpcode() == ISD::CopyFromReg) {
     }
   }
   return N->getSimpleValueType(NumRes);
 }
 
 /// CheckForLiveRegDef - Return true and update live register vector if the
 /// specified register def of the specified SUnit clobbers any "live" registers.
 static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
-                               std::vector<SUnit*> &LiveRegDefs,
+                               const std::vector<SUnit*> &LiveRegDefs,
                                SmallSet<unsigned, 4> &RegAdded,
                                SmallVectorImpl<unsigned> &LRegs,
                                const TargetRegisterInfo *TRI) {
   for (MCRegAliasIterator AliasI(Reg, TRI, true); AliasI.isValid(); ++AliasI) {
 
     // Check if Ref is live.
     if (!LiveRegDefs[*AliasI]) continue;
 
     // Allow multiple uses of the same def.
     if (LiveRegDefs[*AliasI] == SU) continue;
 
     // Add Reg to the set of interfering live regs.
     if (RegAdded.insert(*AliasI).second) {
       LRegs.push_back(*AliasI);
     }
   }
 }
 
 /// CheckForLiveRegDefMasked - Check for any live physregs that are clobbered
 /// by RegMask, and add them to LRegs.
 static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
-                                     std::vector<SUnit*> &LiveRegDefs,
+                                     const std::vector<SUnit*> &LiveRegDefs,
                                      SmallSet<unsigned, 4> &RegAdded,
                                      SmallVectorImpl<unsigned> &LRegs) {
   // Look at all live registers. Skip Reg0 and the special CallResource.
   for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {
     if (!LiveRegDefs[i]) continue;
     if (LiveRegDefs[i] == SU) continue;
     if (!MachineOperand::clobbersPhysReg(RegMask, i)) continue;
     if (RegAdded.insert(i).second)

 }
 
 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
 /// scheduling of the given node to satisfy live physical register dependencies.
 /// If the specific node is the last one that's available to schedule, do
 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
 bool ScheduleDAGRRList::
 DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
-  if (NumLiveRegs == 0)
+  if (LiveRegs.empty())
     return false;
 
   SmallSet<unsigned, 4> RegAdded;
   // If this node would clobber any "live" register, then it's not ready.
   //
   // If SU is the currently live definition of the same register that it uses,
   // then we are free to schedule it.
   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
        I != E; ++I) {
-    if (I->isAssignedRegDep() && LiveRegDefs[I->getReg()] != SU)
-      CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs,
+    if (I->isAssignedRegDep() && LiveRegs.getDef(I->getReg()) != SU)
+      CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegs.getDefs(),
                          RegAdded, LRegs, TRI);
   }
 
   for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
     if (Node->getOpcode() == ISD::INLINEASM) {
       // Inline asm can clobber physical defs.
       unsigned NumOps = Node->getNumOperands();
       if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
         --NumOps;  // Ignore the glue operand.
 
       for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
         unsigned Flags =
           cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
         unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
 
         ++i; // Skip the ID value.
         if (InlineAsm::isRegDefKind(Flags) ||
             InlineAsm::isRegDefEarlyClobberKind(Flags) ||
             InlineAsm::isClobberKind(Flags)) {
           // Check for def of register or earlyclobber register.
           for (; NumVals; --NumVals, ++i) {
             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
             if (TargetRegisterInfo::isPhysicalRegister(Reg))
-              CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
+              CheckForLiveRegDef(SU, Reg, LiveRegs.getDefs(), RegAdded, LRegs, TRI);
           }
         } else
           i += NumVals;
       }
       continue;
     }
 
     if (!Node->isMachineOpcode())
       continue;
     // If we're in the middle of scheduling a call, don't begin scheduling
     // another call. Also, don't allow any physical registers to be live across
     // the call.
     if (Node->getMachineOpcode() == (unsigned)TII->getCallFrameDestroyOpcode()) {
       // Check the special calling-sequence resource.
       unsigned CallResource = TRI->getNumRegs();
-      if (LiveRegDefs[CallResource]) {
-        SDNode *Gen = LiveRegGens[CallResource]->getNode();
+      if (LiveRegs.getCallResourceDef()) {
+        SDNode *Gen = LiveRegs.getCallResourceGen()->getNode();
         while (SDNode *Glued = Gen->getGluedNode())
           Gen = Glued;
         if (!IsChainDependent(Gen, Node, 0, TII) &&
             RegAdded.insert(CallResource).second)
           LRegs.push_back(CallResource);
       }
     }
     if (const uint32_t *RegMask = getNodeRegMask(Node))
-      CheckForLiveRegDefMasked(SU, RegMask, LiveRegDefs, RegAdded, LRegs);
+      CheckForLiveRegDefMasked(SU, RegMask, LiveRegs.getDefs(), RegAdded, LRegs);
 
     const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
     if (!MCID.ImplicitDefs)
       continue;
     for (const uint16_t *Reg = MCID.getImplicitDefs(); *Reg; ++Reg)
-      CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
+      CheckForLiveRegDef(SU, *Reg, LiveRegs.getDefs(), RegAdded, LRegs, TRI);
   }
 
   return !LRegs.empty();
 }
 
 void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {
   // Add the nodes that aren't ready back onto the available list.
   for (unsigned i = Interferences.size(); i > 0; --i) {
for (unsigned i = 0, e = Interferences.size(); i != e; ++i) {
     SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
 
     // Try unscheduling up to the point where it's safe to schedule
     // this node.
     SUnit *BtSU = nullptr;
     unsigned LiveCycle = UINT_MAX;
     for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
       unsigned Reg = LRegs[j];
-      if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
-        BtSU = LiveRegGens[Reg];
+      if (LiveRegs.getGen(Reg)->getHeight() < LiveCycle) {
+        BtSU = LiveRegs.getGen(Reg);
         LiveCycle = BtSU->getHeight();
       }
     }
     if (!WillCreateCycle(TrySU, BtSU))  {
       // BacktrackBottomUp mutates Interferences!
       BacktrackBottomUp(TrySU, BtSU);
 
       // Force the current node to be scheduled before the node that
if (!CurSU) {
     // duplicate the nodes that produces these "too expensive to copy"
     // values to break the dependency. In case even that doesn't work,
     // insert cross class copies.
     // If it's not too expensive, i.e. cost != -1, issue copies.
     SUnit *TrySU = Interferences[0];
     SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
     assert(LRegs.size() == 1 && "Can't handle this yet!");
     unsigned Reg = LRegs[0];
-    SUnit *LRDef = LiveRegDefs[Reg];
+    SUnit *LRDef = LiveRegs.getDef(Reg);
+    assert(LRDef && "LiveRegDef not set");
     MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
     const TargetRegisterClass *RC =
       TRI->getMinimalPhysRegClass(Reg, VT);
     const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
 
     // If cross copy register class is the same as RC, then it must be possible
     // copy the value directly. Do not try duplicate the def.
     // If cross copy register class is not the same as RC, then it's possible to
if (!NewDef) {
       DEBUG(dbgs() << "    Adding an edge from SU #" << TrySU->NodeNum
             << " to SU #" << Copies.front()->NodeNum << "\n");
       AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
       NewDef = Copies.back();
     }
 
     DEBUG(dbgs() << "    Adding an edge from SU #" << NewDef->NodeNum
           << " to SU #" << TrySU->NodeNum << "\n");
-    LiveRegDefs[Reg] = NewDef;
+    LiveRegs.setDef(Reg, NewDef);
     AddPred(NewDef, SDep(TrySU, SDep::Artificial));
     TrySU->isAvailable = false;
     CurSU = NewDef;
   }
   assert(CurSU && "Unable to resolve live physical register dependencies!");
   return CurSU;
 }