[NFC][ScheduleDAG] Remove unused EntrySU SUnit

[thegameg]

Summary

EntrySU doesn't seem to be used at all when building the ScheduleDAG.

[dmgreen]

Sounds good to me.

[fhahn]

This looks indeed unused, thanks for cleaning this up! There may be downstream targets that make use of EntrySU, but if that's the case it is easy to revert.

LGTM

[materi]

Our out-of-tree backend is currently using EntrySU for working with inter-region latencies.

When there is a long latency between two regions, we add an artificial edge from EntrySU to the successor SU with the appropriate latency. Then the scheduler has a chance to avoid the stall. The scheduler here is a custom out-of-tree variant for our in-order VLIW target.

If EntrySU is removed we would have to work on another way to handle these types of latencies. Does anyone know of a simpler or better way of doing it?

[npjdesres]

I also maintain an out-of-tree backend that relied on the EntrySU. Like materi, I used it to track inter-region latencies. I would be happy to update my code track these latencies in some other way. Please advise. Thanks

[thegameg]

I am totally fine with keeping this in-tree, even unused, if it helps several out-of-tree backends. Thanks for speaking up.

Maybe someone using it can provide an explanation of potential uses of this node as a comment in ScheduleDAG.h?

[fhahn]

In D87867#2285957, @thegameg wrote:

I am totally fine with keeping this in-tree, even unused, if it helps several out-of-tree backends. Thanks for speaking up.

Maybe someone using it can provide an explanation of potential uses of this node as a comment in ScheduleDAG.h?

It's perfectly fine to keep it, but it would be good to have something use it in tree upstream, otherwise we have zero test coverage.

[hgreving]

Our backend is using EntrySU the same way as described by another poster above: to add top edges to adjust for clearances to the basic block entry. When removing this, we need to add our own EntrySU, but this becomes tricky because the scheduler will try to schedule it and release the node. I think it does make sense to keep EntrySU in-tree. Thanks for that.

llvm/include/llvm/CodeGen/MachineScheduler.h

public:
 
   /// Tell the strategy that MBB is about to be processed.
   virtual void enterMBB(MachineBasicBlock *MBB) {};
 
   /// Tell the strategy that current MBB is done.
   virtual void leaveMBB() {};
 
   /// Notify this strategy that all roots have been released (including those
-  /// that depend on EntrySU or ExitSU).
+  /// that depend on ExitSU).
   virtual void registerRoots() {}
 
   /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
   /// schedule the node at the top of the unscheduled region. Otherwise it will
   /// be scheduled at the bottom.
   virtual SUnit *pickNode(bool &IsTopNode) = 0;
 
   /// Scheduler callback to notify that a new subtree is scheduled.

llvm/include/llvm/CodeGen/ScheduleDAG.h

class TargetRegisterInfo;
   class ScheduleDAG {
   public:
     const LLVMTargetMachine &TM;        ///< Target processor
     const TargetInstrInfo *TII;         ///< Target instruction information
     const TargetRegisterInfo *TRI;      ///< Target processor register info
     MachineFunction &MF;                ///< Machine function
     MachineRegisterInfo &MRI;           ///< Virtual/real register map
     std::vector<SUnit> SUnits;          ///< The scheduling units.
-    SUnit EntrySU;                      ///< Special node for the region entry.
     SUnit ExitSU;                       ///< Special node for the region exit.
 
 #ifdef NDEBUG
     static const bool StressSched = false;
 #else
     bool StressSched;
 #endif
 

llvm/lib/CodeGen/MachineScheduler.cpp

#ifndef NDEBUG
   }
 #endif
   // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However,
   // CurrCycle may have advanced since then.
   if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency())
     PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency();
 
   --PredSU->NumSuccsLeft;
-  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
+  if (PredSU->NumSuccsLeft == 0)
     SchedImpl->releaseBottomNode(PredSU);
 }
 
 /// releasePredecessors - Call releasePred on each of SU's predecessors.
 void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
   for (SDep &Pred : SU->Preds)
     releasePred(SU, &Pred);
 }

 }
 
 /// Identify DAG roots and setup scheduler queues.
 void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots,
                                ArrayRef<SUnit*> BotRoots) {
   NextClusterSucc = nullptr;
   NextClusterPred = nullptr;
 
-  // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
+  // Release all DAG roots for scheduling, not including ExitSU.
   //
   // Nodes with unreleased weak edges can still be roots.
   // Release top roots in forward order.
   for (SUnit *SU : TopRoots)
     SchedImpl->releaseTopNode(SU);
 
   // Release bottom roots in reverse order so the higher priority nodes appear
   // first. This is more natural and slightly more efficient.
   for (SmallVectorImpl<SUnit*>::const_reverse_iterator
          I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {
     SchedImpl->releaseBottomNode(*I);
   }
 
-  releaseSuccessors(&EntrySU);
   releasePredecessors(&ExitSU);
 
   SchedImpl->registerRoots();
 
   // Advance past initial DebugValues.
   CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
   CurrentBottom = RegionEnd;
 }
if (ShouldTrackLaneMasks) {
         }
       }
     }
   }
 }
 
 void ScheduleDAGMILive::dump() const {
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  if (EntrySU.getInstr() != nullptr)
-    dumpNodeAll(EntrySU);
   for (const SUnit &SU : SUnits) {
     dumpNodeAll(SU);
     if (ShouldTrackPressure) {
       dbgs() << "  Pressure Diff      : ";
       getPressureDiff(&SU).dump(*TRI);
     }
     dbgs() << "  Single Issue       : ";
     if (SchedModel.mustBeginGroup(SU.getInstr()) &&

llvm/lib/CodeGen/MacroFusion.cpp

for (const SDep &SI : FirstSU.Succs) {
         continue;
       LLVM_DEBUG(dbgs() << "  Bind "; DAG.dumpNodeName(SecondSU);
                  dbgs() << " - "; DAG.dumpNodeName(*SU); dbgs() << '\n';);
       DAG.addEdge(SU, SDep(&SecondSU, SDep::Artificial));
     }
 
   // Make the FirstSU also dependent on the dependencies of the SecondSU to
   // prevent them from being scheduled between the FirstSU and the SecondSU.
-  if (&FirstSU != &DAG.EntrySU) {
-    for (const SDep &SI : SecondSU.Preds) {
-      SUnit *SU = SI.getSUnit();
-      if (SI.isWeak() || isHazard(SI) || &FirstSU == SU || FirstSU.isSucc(SU))
-        continue;
-      LLVM_DEBUG(dbgs() << "  Bind "; DAG.dumpNodeName(*SU); dbgs() << " - ";
-                 DAG.dumpNodeName(FirstSU); dbgs() << '\n';);
-      DAG.addEdge(&FirstSU, SDep(SU, SDep::Artificial));
-    }
-    // ExitSU comes last by design, which acts like an implicit dependency
-    // between ExitSU and any bottom root in the graph. We should transfer
-    // this to FirstSU as well.
-    if (&SecondSU == &DAG.ExitSU) {
-      for (SUnit &SU : DAG.SUnits) {
-        if (SU.Succs.empty())
-          DAG.addEdge(&FirstSU, SDep(&SU, SDep::Artificial));
-      }
-    }
-  }
 
   ++NumFused;
   return true;
 }
 
 namespace {
 
 /// Post-process the DAG to create cluster edges between instrs that may

llvm/lib/CodeGen/PostRASchedulerList.cpp

void SchedulePostRATDList::ListScheduleTopDown() {
   unsigned CurCycle = 0;
 
   // We're scheduling top-down but we're visiting the regions in
   // bottom-up order, so we don't know the hazards at the start of a
   // region. So assume no hazards (this should usually be ok as most
   // blocks are a single region).
   HazardRec->Reset();
 
-  // Release any successors of the special Entry node.
-  ReleaseSuccessors(&EntrySU);
-
   // Add all leaves to Available queue.
   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     // It is available if it has no predecessors.
     if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
       AvailableQueue.push(&SUnits[i]);
       SUnits[i].isAvailable = true;
     }
   }

llvm/lib/CodeGen/ScheduleDAG.cpp

#ifndef NDEBUG
   StressSched = StressSchedOpt;
 #endif
 }
 
 ScheduleDAG::~ScheduleDAG() = default;
 
 void ScheduleDAG::clearDAG() {
   SUnits.clear();
-  EntrySU = SUnit();
   ExitSU = SUnit();
 }
 
 const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {
   if (!Node || !Node->isMachineOpcode()) return nullptr;
   return &TII->get(Node->getMachineOpcode());
 }
 
if (WeakSuccsLeft)
     dbgs() << "  # weak succs left  : " << WeakSuccsLeft << "\n";
   dbgs() << "  # rdefs left       : " << NumRegDefsLeft << "\n";
   dbgs() << "  Latency            : " << Latency << "\n";
   dbgs() << "  Depth              : " << getDepth() << "\n";
   dbgs() << "  Height             : " << getHeight() << "\n";
 }
 
 LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeName(const SUnit &SU) const {
-  if (&SU == &EntrySU)
-    dbgs() << "EntrySU";
-  else if (&SU == &ExitSU)
+  if (&SU == &ExitSU)
     dbgs() << "ExitSU";
   else
     dbgs() << "SU(" << SU.NodeNum << ")";
 }
 
 LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {
   dumpNode(SU);
   SU.dumpAttributes();
std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
   // passes are added to Nodes.
   WorkList.push_back(&TargetSU);
   do {
     const SUnit *SU = WorkList.back();
     WorkList.pop_back();
     for (int I = SU->Preds.size()-1; I >= 0; --I) {
       const SUnit *Pred = SU->Preds[I].getSUnit();
       unsigned s = Pred->NodeNum;
-      // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
+      // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
       if (Pred->isBoundaryNode())
         continue;
       if (Node2Index[s] == LowerBound) {
         Found = true;
         continue;
       }
       if (!VisitedBack.test(s) && Visited.test(s)) {
         VisitedBack.set(s);

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   dumpNodeName(SU);
   dbgs() << ": ";
   SU.getInstr()->dump();
 #endif
 }
 
 void ScheduleDAGInstrs::dump() const {
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  if (EntrySU.getInstr() != nullptr)
-    dumpNodeAll(EntrySU);
   for (const SUnit &SU : SUnits)
     dumpNodeAll(SU);
   if (ExitSU.getInstr() != nullptr)
     dumpNodeAll(ExitSU);
 #endif
 }
 
 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
   std::string s;
   raw_string_ostream oss(s);
-  if (SU == &EntrySU)
-    oss << "<entry>";
-  else if (SU == &ExitSU)
+  if (SU == &ExitSU)
     oss << "<exit>";
   else
     SU->getInstr()->print(oss, /*SkipOpers=*/true);
   return oss.str();
 }
 
 /// Return the basic block label. It is not necessarilly unique because a block
 /// contains multiple scheduling regions. But it is fine for visualization.

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGFast.cpp

if (PredSU->NumSuccsLeft == 0) {
     dumpNode(*PredSU);
     dbgs() << " has been released too many times!\n";
     llvm_unreachable(nullptr);
   }
 #endif
   --PredSU->NumSuccsLeft;
 
   // If all the node's successors are scheduled, this node is ready
-  // to be scheduled. Ignore the special EntrySU node.
-  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
+  // to be scheduled.
+  if (PredSU->NumSuccsLeft == 0) {
     PredSU->isAvailable = true;
     AvailableQueue.push(PredSU);
   }
 }
 
 void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
   // Bottom up: release predecessors
   for (SDep &Pred : SU->Preds) {

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

#endif
 
   if (!forceUnitLatencies()) {
     // Updating predecessor's height. This is now the cycle when the
     // predecessor can be scheduled without causing a pipeline stall.
     PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
   }
 
   // If all the node's successors are scheduled, this node is ready
-  // to be scheduled. Ignore the special EntrySU node.
-  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
+  // to be scheduled.
+  if (PredSU->NumSuccsLeft == 0) {
     PredSU->isAvailable = true;
 
     unsigned Height = PredSU->getHeight();
     if (Height < MinAvailableCycle)
       MinAvailableCycle = Height;
 
     if (isReady(PredSU)) {
       AvailableQueue->push(PredSU);

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

while (!GluedNodes.empty()) {
     dbgs() << "\n";
     GluedNodes.pop_back();
   }
 #endif
 }
 
 void ScheduleDAGSDNodes::dump() const {
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-  if (EntrySU.getNode() != nullptr)
-    dumpNodeAll(EntrySU);
   for (const SUnit &SU : SUnits)
     dumpNodeAll(SU);
   if (ExitSU.getNode() != nullptr)
     dumpNodeAll(ExitSU);
 #endif
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGVLIW.cpp

void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
   AvailableQueue->scheduledNode(SU);
 }
 
 /// listScheduleTopDown - The main loop of list scheduling for top-down
 /// schedulers.
 void ScheduleDAGVLIW::listScheduleTopDown() {
   unsigned CurCycle = 0;
 
-  // Release any successors of the special Entry node.
-  releaseSuccessors(&EntrySU);
-
   // All leaves to AvailableQueue.
   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
     // It is available if it has no predecessors.
     if (SUnits[i].Preds.empty()) {
       AvailableQueue->push(&SUnits[i]);
       SUnits[i].isAvailable = true;
     }
   }

llvm/lib/Target/AMDGPU/GCNMinRegStrategy.cpp

GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
 
   initNumPreds(SUnits);
 
   int StepNo = 0;
 
   for (auto SU : TopRoots) {
     RQ.push_back(*new (Alloc.Allocate()) Candidate(SU, StepNo));
   }
-  releaseSuccessors(&DAG.EntrySU, StepNo);
 
   while (!RQ.empty()) {
     LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
                       << "\n"
                          "Ready queue:";
                for (auto &C
                     : RQ) dbgs()
                << ' ' << C.SU->NodeNum << "(P" << C.Priority << ')';

llvm/lib/Target/AMDGPU/SIMachineScheduler.h

public:
 
   MachineBasicBlock *getBB() { return BB; }
   MachineBasicBlock::iterator getCurrentTop() { return CurrentTop; }
   MachineBasicBlock::iterator getCurrentBottom() { return CurrentBottom; }
   LiveIntervals *getLIS() { return LIS; }
   MachineRegisterInfo *getMRI() { return &MRI; }
   const TargetRegisterInfo *getTRI() { return TRI; }
   ScheduleDAGTopologicalSort *GetTopo() { return &Topo; }
-  SUnit& getEntrySU() { return EntrySU; }
   SUnit& getExitSU() { return ExitSU; }
 
   void restoreSULinksLeft();
 
   template<typename _Iterator> void fillVgprSgprCost(_Iterator First,
                                                      _Iterator End,
                                                      unsigned &VgprUsage,
                                                      unsigned &SgprUsage);