Revert "[NFC][ScheduleDAG] Remove unused EntrySU SUnit"

[pifon2a]

Summary

This reverts commit 0345d88de654259ae90494bf9b015416e2cccacb.

Google internal backend uses EntrySU, we are looking into removing dependency on it.

[pifon2a]

Update description.

[bkramer]

Ok, let's revert this for now. It's annoying to have a dependency on something that's not used by the in-tree backends, so we need to figure out how to remove it.

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 ExitSU).
+  /// that depend on EntrySU or 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)
+  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
     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 ExitSU.
+  // Release all DAG roots for scheduling, not including EntrySU/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 == &ExitSU)
+  if (&SU == &EntrySU)
+    dbgs() << "EntrySU";
+  else 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. ExitSU).
+      // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
       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 == &ExitSU)
+  if (SU == &EntrySU)
+    oss << "<entry>";
+  else if (SU == &ExitSU)
     oss << "<exit>";
   else
     SU->getInstr()->print(oss, /*IsStandalone=*/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.
-  if (PredSU->NumSuccsLeft == 0) {
+  // to be scheduled. Ignore the special EntrySU node.
+  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
     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.
-  if (PredSU->NumSuccsLeft == 0) {
+  // to be scheduled. Ignore the special EntrySU node.
+  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
     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);