[PowerPC] Forward the scheduling state for PowerPC target

[steven.zhang]

Summary

The patch https://reviews.llvm.org/D61248 add the scheduling state forward infrastructure, and the patch https://reviews.llvm.org/D59480 add the sched state structure to keep the scheduling state. This patch bases on these two patches, and enable the scheduling state forward for PostGenericScheduler.
Then, enable it for powerpc target.

[fhahn]

Would it be possible to add a test where the forwarding kicks in?

[steven.zhang]

In D61250#1545597, @fhahn wrote:

Would it be possible to add a test where the forwarding kicks in?

It is not easy. We could easily get some tests that have different code sequence if enable the fwd scheduling, however, it is not easy to explain why, and if that makes sense. Because, we have so many heuristic that works together to get the final order. Anyway, I will try my best to cook one, Thank you for this suggestion!

llvm/include/llvm/CodeGen/MachineScheduler.h

private:
   /// Scheduling resource state.
   SchedState State;
 
 public:
   /// Pending queues extend the ready queues with the same ID and the
   /// PendingFlag set.
   SchedBoundary(unsigned ID, const Twine &Name):
     Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
-    reset();
+    reset(SchedState());
   }
 
   ~SchedBoundary();
 
-  void reset();
+  void reset(const SchedState &S);
 
   const SchedState &getState() const { return State; }
   void setState(const SchedState &State) { this->State = State; }
 
   void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
-            SchedRemainder *rem);
+            SchedRemainder *rem, const SchedState *State);
 
   bool isTop() const {
     return Available.getID() == TopQID;
   }
 
   /// Number of cycles to issue the instructions scheduled in this zone.
   unsigned getCurrCycle() const { return State.CurrCycle; }
 

 /// Callbacks from ScheduleDAGMI:
 ///   initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
 class PostGenericScheduler : public GenericSchedulerBase {
 protected:
   ScheduleDAGMI *DAG;
   SchedBoundary Top;
   SmallVector<SUnit*, 8> BotRoots;
 
+  typedef DenseMap<MachineBasicBlock*, SchedState*> MBB2StateRec;
+  MBB2StateRec SchedStates;
 public:
   PostGenericScheduler(const MachineSchedContext *C):
     GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
 
-  ~PostGenericScheduler() override = default;
+  ~PostGenericScheduler() override;
 
   void initPolicy(MachineBasicBlock::iterator Begin,
                   MachineBasicBlock::iterator End,
                   unsigned NumRegionInstrs) override {
     /* no configurable policy */
   }
 
   /// PostRA scheduling does not track pressure.
void releaseTopNode(SUnit *SU) override {
     Top.releaseNode(SU, SU->TopReadyCycle);
   }
 
   // Only called for roots.
   void releaseBottomNode(SUnit *SU) override {
     BotRoots.push_back(SU);
   }
 
+  bool saveScheduledState(MachineBasicBlock *MBB) override;
+
+  bool restoreScheduledState(MachineBasicBlock *MBB) override;
+
+  void enterMBB(MachineBasicBlock *MBB) override;
 protected:
   void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
 
   void pickNodeFromQueue(SchedCandidate &Cand);
 };
 
 /// Create the standard converging machine scheduler. This will be used as the
 /// default scheduler if the target does not set a default.

llvm/lib/CodeGen/MachineScheduler.cpp

 
 /// Given a Count of resource usage and a Latency value, return true if a
 /// SchedBoundary becomes resource limited.
 static bool checkResourceLimit(unsigned LFactor, unsigned Count,
                                unsigned Latency) {
   return (int)(Count - (Latency * LFactor)) > (int)LFactor;
 }
 
-void SchedBoundary::reset() {
+void SchedBoundary::reset(const SchedState &S) {
   // A new HazardRec is created for each DAG and owned by SchedBoundary.
   // Destroying and reconstructing it is very expensive though. So keep
   // invalid, placeholder HazardRecs.
   if (HazardRec && HazardRec->isEnabled()) {
     delete HazardRec;
     HazardRec = nullptr;
   }
   Available.clear();
   Pending.clear();
   CheckPending = false;
 
-  State = SchedState();
+  State = S;
 }
 
 void SchedRemainder::
 init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
   reset();
   if (!SchedModel->hasInstrSchedModel())
     return;
   RemainingCounts.resize(SchedModel->getNumProcResourceKinds());
   for (SUnit &SU : DAG->SUnits) {
     const MCSchedClassDesc *SC = DAG->getSchedClass(&SU);
     RemIssueCount += SchedModel->getNumMicroOps(SU.getInstr(), SC)
       * SchedModel->getMicroOpFactor();
     for (TargetSchedModel::ProcResIter
            PI = SchedModel->getWriteProcResBegin(SC),
            PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
       unsigned PIdx = PI->ProcResourceIdx;
       unsigned Factor = SchedModel->getResourceFactor(PIdx);
       RemainingCounts[PIdx] += (Factor * PI->Cycles);
     }
   }
 }
 
 void SchedBoundary::
-init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
-  reset();
+init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem,
+     const SchedState *SS) {
+  reset(SS ? *SS : SchedState());
   DAG = dag;
   SchedModel = smodel;
   Rem = rem;
   if (SchedModel->hasInstrSchedModel()) {
     State.ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds());
     State.ReservedCycles.resize(SchedModel->getNumProcResourceKinds(), 
                                 InvalidCycle);
   }

 void GenericScheduler::initialize(ScheduleDAGMI *dag) {
   assert(dag->hasVRegLiveness() &&
          "(PreRA)GenericScheduler needs vreg liveness");
   DAG = static_cast<ScheduleDAGMILive*>(dag);
   SchedModel = DAG->getSchedModel();
   TRI = DAG->TRI;
 
   Rem.init(DAG, SchedModel);
-  Top.init(DAG, SchedModel, &Rem);
-  Bot.init(DAG, SchedModel, &Rem);
+  Top.init(DAG, SchedModel, &Rem, nullptr);
+  Bot.init(DAG, SchedModel, &Rem, nullptr);
 
   // Initialize resource counts.
 
   // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
   // are disabled, then these HazardRecs will be disabled.
   const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
   if (!Top.HazardRec) {
     Top.HazardRec =

 static MachineSchedRegistry
 GenericSchedRegistry("converge", "Standard converging scheduler.",
                      createConveringSched);
 
 //===----------------------------------------------------------------------===//
 // PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
 //===----------------------------------------------------------------------===//
 
+// Check if this is the first region of the MBB topdown.
+static bool isFirstRegion(ScheduleDAGMI *DAG) {
+  return DAG->begin() == DAG->begin()->getParent()->begin();
+}
+
 void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
   DAG = Dag;
   SchedModel = DAG->getSchedModel();
   TRI = DAG->TRI;
 
   Rem.init(DAG, SchedModel);
-  Top.init(DAG, SchedModel, &Rem);
+  // The sched state in first region has been intialized when enter the MBB.
+  Top.init(DAG, SchedModel, &Rem,
+           isFirstRegion(DAG) ? &Top.getState() : nullptr);
   BotRoots.clear();
 
   // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
   // or are disabled, then these HazardRecs will be disabled.
   const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
   if (!Top.HazardRec) {
     Top.HazardRec =
         DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
   IsTopNode = true;
   Top.removeReady(SU);
 
   LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
                     << *SU->getInstr());
   return SU;
 }
 
+PostGenericScheduler::~PostGenericScheduler() {
+  for (auto State : SchedStates)
+    delete State.second;
+}
+
+bool PostGenericScheduler::saveScheduledState(MachineBasicBlock *MBB) {
+  SchedStates[MBB] = new SchedState(Top.getState());
+  return true;
+}
+
+bool PostGenericScheduler::restoreScheduledState(MachineBasicBlock *MBB) {
+  if (SchedStates.find(MBB) != SchedStates.end()) {
+    Top.setState(*SchedStates[MBB]);
+    return true;
+   }
+  return false;
+}
+
+void PostGenericScheduler::enterMBB(MachineBasicBlock *MBB) {
+  Top.setState(SchedState());
+}
+
 /// Called after ScheduleDAGMI has scheduled an instruction and updated
 /// scheduled/remaining flags in the DAG nodes.
 void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
   SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
   Top.bumpNode(SU);
 }
 
 ScheduleDAGMI *llvm::createGenericSchedPostRA(MachineSchedContext *C) {

llvm/lib/Target/PowerPC/PPCSubtarget.h

public:
   bool isDarwinABI() const { return isTargetMachO() || isDarwin(); }
   bool isSVR4ABI() const { return !isDarwinABI(); }
   bool isELFv2ABI() const;
 
   /// Originally, this function return hasISEL(). Now we always enable it,
   /// but may expand the ISEL instruction later.
   bool enableEarlyIfConversion() const override { return true; }
 
+  bool forwardScheduledState() const override { return true; }
+
   // Scheduling customization.
   bool enableMachineScheduler() const override;
   // This overrides the PostRAScheduler bit in the SchedModel for each CPU.
   bool enablePostRAScheduler() const override;
   AntiDepBreakMode getAntiDepBreakMode() const override;
   void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const override;
 
   void overrideSchedPolicy(MachineSchedPolicy &Policy,