Add macro-fusion hook in MIScheduler and support cluster instructions scheduling in PostRAScheduler

[nemanjai]

Summary

• Allow targets plug their own macro-fusion logic to replace default one in default pre-scheduler (i.e. ScheduleDAGMILive).
• Teach PostRAScheduler being able to schedule cluster instructions in adjacent fashion.

[amehsan]

lib/CodeGen/MachineScheduler.cpp

3108–3129

Why not adding Target specific code to create scheduler objects and add any mutations that we need, there? What we want to do here, is Target specific and I think sooner or later we will have other target specific requirements to satisfy when creating scheduler, strategy and mutations. Why do you want to do this here?

lib/CodeGen/PostRASchedulerList.cpp

465–471

I have doubts that we need to make any changes in this file. We want to switch to post-ra MIScheduler. So I don't see much benefit in making changes here.

[cycheng]

lib/CodeGen/MachineScheduler.cpp

3108–3129

Because EnableMacroFusion is true by default, so we will call MacroFusion::apply by default, also it looks like a general feature across different targets, so I think we should also be able to hook customized MacroFusion for different targets.

[amehsan]

For two of the three files that I checked, the changes here appear in D22194 as well. Did you mean to abandon this patch and use D22194 instead?

[cycheng]

In D22193#486343, @amehsan wrote:

For two of the three files that I checked, the changes here appear in D22194 as well. Did you mean to abandon this patch and use D22194 instead?

No, because D22194 is depend on D22193, I don't know whether I can make a diff based on D22193, so I just make both patches against on master.
Is there any more appropriate way to express this kind of dependency on Phabricator?

[nemanjai]

There are no current plans to implement fusion. Abandoning this patch.

include/llvm/CodeGen/TargetPassConfig.h

 #include "llvm/Pass.h"
 #include "llvm/Support/CodeGen.h"
 #include <string>
 
 namespace llvm {
 
 class PassConfigImpl;
 class ScheduleDAGInstrs;
+class ScheduleDAGMutation;
 class TargetMachine;
 struct MachineSchedContext;
 
 // The old pass manager infrastructure is hidden in a legacy namespace now.
 namespace legacy {
 class PassManagerBase;
 }
 using legacy::PassManagerBase;
public:
 
   /// Similar to createMachineScheduler but used when postRA machine scheduling
   /// is enabled.
   virtual ScheduleDAGInstrs *
   createPostMachineScheduler(MachineSchedContext *C) const {
     return nullptr;
   }
 
+  /// When EnableMacroFusion is true, create target defined MacroFusion
+  /// instance to be run within default pre-scheduler.
+  ///
+  /// Return NULL to select the default MacroFusion.
+  virtual ScheduleDAGMutation *
+  createMacroFusion(ScheduleDAGInstrs *DAG) const {
+    return nullptr;
+  }
+
   /// printAndVerify - Add a pass to dump then verify the machine function, if
   /// those steps are enabled.
   ///
   void printAndVerify(const std::string &Banner);
 
   /// Add a pass to print the machine function if printing is enabled.
   void addPrintPass(const std::string &Banner);
 

lib/CodeGen/MachineScheduler.cpp

if (IsTopNode) {
     Bot.bumpNode(SU);
     if (SU->hasPhysRegDefs)
       reschedulePhysRegCopies(SU, false);
   }
 }
 
 /// Create the standard converging machine scheduler. This will be used as the
 /// default scheduler if the target does not set a default.
 static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C) {
   ScheduleDAGMILive *DAG = new ScheduleDAGMILive(C, make_unique<GenericScheduler>(C));
   // Register DAG post-processors.
   //
   // FIXME: extend the mutation API to allow earlier mutations to instantiate
   // data and pass it to later mutations. Have a single mutation that gathers
   // the interesting nodes in one pass.
   DAG->addMutation(make_unique<CopyConstrain>(DAG->TII, DAG->TRI));
   if (EnableMemOpCluster) {
     if (DAG->TII->enableClusterLoads())
       DAG->addMutation(make_unique<LoadClusterMutation>(DAG->TII, DAG->TRI));
     if (DAG->TII->enableClusterStores())
       DAG->addMutation(make_unique<StoreClusterMutation>(DAG->TII, DAG->TRI));
   }
-  if (EnableMacroFusion)
+  if (EnableMacroFusion) {
+    if (ScheduleDAGMutation *Fusion = C->PassConfig->createMacroFusion(DAG))
+      DAG->addMutation(std::unique_ptr<ScheduleDAGMutation>(Fusion));
+    else
       DAG->addMutation(make_unique<MacroFusion>(*DAG->TII, *DAG->TRI));
+  }
   return DAG;
 }
 
 static MachineSchedRegistry
 GenericSchedRegistry("converge", "Standard converging scheduler.",
                      createGenericSchedLive);
 
 //===----------------------------------------------------------------------===//
 // PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
 //===----------------------------------------------------------------------===//

lib/CodeGen/PostRASchedulerList.cpp

class SchedulePostRATDList : public ScheduleDAGInstrs {
     LatencyPriorityQueue AvailableQueue;
 
     /// PendingQueue - This contains all of the instructions whose operands have
     /// been issued, but their results are not ready yet (due to the latency of
     /// the operation).  Once the operands becomes available, the instruction is
     /// added to the AvailableQueue.
     std::vector<SUnit*> PendingQueue;
 
+    /// Record the next node in a scheduled cluster.
+    SUnit *NextClusterSucc;
+
     /// HazardRec - The hazard recognizer to use.
     ScheduleHazardRecognizer *HazardRec;
 
     /// AntiDepBreak - Anti-dependence breaking object, or NULL if none
     AntiDepBreaker *AntiDepBreak;
 
     /// AA - AliasAnalysis for making memory reference queries.
     AliasAnalysis *AA;

 INITIALIZE_PASS(PostRAScheduler, "post-RA-sched",
                 "Post RA top-down list latency scheduler", false, false)
 
 SchedulePostRATDList::SchedulePostRATDList(
     MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA,
     const RegisterClassInfo &RCI,
     TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
     SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
-    : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
-
+    : ScheduleDAGInstrs(MF, &MLI), NextClusterSucc(nullptr), AA(AA), EndIndex(0)
+{
   const InstrItineraryData *InstrItins =
       MF.getSubtarget().getInstrItineraryData();
   HazardRec =
       MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
           InstrItins, this);
   MF.getSubtarget().getPostRAMutations(Mutations);
 
   assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||

 //  Top-Down Scheduling
 //===----------------------------------------------------------------------===//
 
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 /// the PendingQueue if the count reaches zero.
 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
   SUnit *SuccSU = SuccEdge->getSUnit();
 
   if (SuccEdge->isWeak()) {
     --SuccSU->WeakPredsLeft;
+    // Cluster instructions get higher scheduling priority.
+    // If SuccSU is not blocked by any other predecessors, let scheduler pick
+    // SuccSU as next scheduling instruction.
+    if (SuccEdge->isCluster() && SuccSU->NumPredsLeft == 0)
+      NextClusterSucc = SuccSU;
     return;
   }
 #ifndef NDEBUG
   if (SuccSU->NumPredsLeft == 0) {
     dbgs() << "*** Scheduling failed! ***\n";
     SuccSU->dump(this);
     dbgs() << " has been released too many times!\n";
     llvm_unreachable(nullptr);
if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
       SUnits[i].isAvailable = true;
     }
   }
 
   // In any cycle where we can't schedule any instructions, we must
   // stall or emit a noop, depending on the target.
   bool CycleHasInsts = false;
 
+  assert(!NextClusterSucc && "Incorrect scheduling state.");
+
   // While Available queue is not empty, grab the node with the highest
   // priority. If it is not ready put it back.  Schedule the node.
   std::vector<SUnit*> NotReady;
   Sequence.reserve(SUnits.size());
   while (!AvailableQueue.empty() || !PendingQueue.empty()) {
+    SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
+    bool HasNoopHazards = false;
+
+    // Clustered instructions get higher scheduling priority, because processor
+    // can work efficiently if these instructions can be scheduled nearby, so
+    // if we have clustered instructions, scheduling them first.
+    if (NextClusterSucc) {
+      // Wait until we have correct cycle count and no more hazard.
+      if (NextClusterSucc->getDepth() <= CurCycle &&
+          HazardRec->getHazardType(NextClusterSucc, 0/*no stalls*/) ==
+          ScheduleHazardRecognizer::NoHazard) {
+        for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i)
+          if (PendingQueue[i] == NextClusterSucc) {
+            PendingQueue.erase(PendingQueue.begin() + i);
+            break;
+          }
+
+        FoundSUnit = NextClusterSucc;
+        NextClusterSucc->isAvailable = true;
+        NextClusterSucc = nullptr;
+      }
+    } else {
       // Check to see if any of the pending instructions are ready to issue.  If
       // so, add them to the available queue.
       unsigned MinDepth = ~0u;
       for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
         if (PendingQueue[i]->getDepth() <= CurCycle) {
           AvailableQueue.push(PendingQueue[i]);
           PendingQueue[i]->isAvailable = true;
           PendingQueue[i] = PendingQueue.back();
           PendingQueue.pop_back();
           --i; --e;
         } else if (PendingQueue[i]->getDepth() < MinDepth)
           MinDepth = PendingQueue[i]->getDepth();
       }
 
       DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this));
 
-    SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr;
-    bool HasNoopHazards = false;
       while (!AvailableQueue.empty()) {
         SUnit *CurSUnit = AvailableQueue.pop();
 
         ScheduleHazardRecognizer::HazardType HT =
           HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
         if (HT == ScheduleHazardRecognizer::NoHazard) {
           if (HazardRec->ShouldPreferAnother(CurSUnit)) {
             if (!NotPreferredSUnit) {
               // If this is the first non-preferred node for this cycle, then
               // record it and continue searching for a preferred node. If this
               // is not the first non-preferred node, then treat it as though
               // there had been a hazard.
               NotPreferredSUnit = CurSUnit;
               continue;
             }
           } else {
             FoundSUnit = CurSUnit;
             break;
           }
         }
 
         // Remember if this is a noop hazard.
         HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
 
         NotReady.push_back(CurSUnit);
       }
+    }
 
     // If we have a non-preferred node, push it back onto the available list.
     // If we did not find a preferred node, then schedule this first
     // non-preferred node.
     if (NotPreferredSUnit) {
       if (!FoundSUnit) {
         DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n");
         FoundSUnit = NotPreferredSUnit;