lib/Target/SystemZ/SystemZMachineScheduler.cpp

   1 //-- SystemZMachineScheduler.cpp - SystemZ Scheduler Interface -*- C++ -*---==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // -------------------------- Post RA scheduling ---------------------------- //
  10 // SystemZPostRASchedStrategy is a scheduling strategy which is plugged into
  11 // the MachineScheduler. It has a sorted Available set of SUs and a pickNode()
  12 // implementation that looks to optimize decoder grouping and balance the
  13 // usage of processor resources. Scheduler states are saved for the end
  14 // region of each MBB, so that a successor block can learn from it.
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "SystemZMachineScheduler.h"
  18 #include "llvm/CodeGen/MachineLoopInfo.h"
  19
  20 using namespace llvm;
  21
  22 #define DEBUG_TYPE "machine-scheduler"
  23
  24 #ifndef NDEBUG
  25 // Print the set of SUs
  26 void SystemZPostRASchedStrategy::SUSet::
  27 dump(SystemZHazardRecognizer &HazardRec) const {
  28   dbgs() << "{";
  29   for (auto &SU : *this) {
  30     HazardRec.dumpSU(SU, dbgs());
  31     if (SU != *rbegin())
  32       dbgs() << ",  ";
  33   }
  34   dbgs() << "}\n";
  35 }
  36 #endif
  37
  38 // Try to find a single predecessor that would be interesting for the
  39 // scheduler in the top-most region of MBB.
  40 static MachineBasicBlock *getSingleSchedPred(MachineBasicBlock *MBB,
  41                                              const MachineLoop *Loop) {
  42   MachineBasicBlock *PredMBB = nullptr;
  43   if (MBB->pred_size() == 1)
  44     PredMBB = *MBB->pred_begin();
  45
  46   // The loop header has two predecessors, return the latch, but not for a
  47   // single block loop.
  48   if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {
  49     for (auto I = MBB->pred_begin(); I != MBB->pred_end(); ++I)
  50       if (Loop->contains(*I))
  51         PredMBB = (*I == MBB ? nullptr : *I);
  52   }
  53
  54   assert ((PredMBB == nullptr || !Loop || Loop->contains(PredMBB))
  55           && "Loop MBB should not consider predecessor outside of loop.");
  56
  57   return PredMBB;
  58 }
  59
  60 void SystemZPostRASchedStrategy::
  61 advanceTo(MachineBasicBlock::iterator NextBegin) {
  62   MachineBasicBlock::iterator LastEmittedMI = HazardRec->getLastEmittedMI();
  63   MachineBasicBlock::iterator I =
  64     ((LastEmittedMI != nullptr && LastEmittedMI->getParent() == MBB) ?
  65      std::next(LastEmittedMI) : MBB->begin());
  66
  67   for (; I != NextBegin; ++I) {
  68     if (I->isPosition() || I->isDebugInstr())
  69       continue;
  70     HazardRec->emitInstruction(&*I);
  71   }
  72 }
  73
  74 void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {
  75   LLVM_DEBUG(HazardRec->dumpState(););
  76 }
  77
  78 void SystemZPostRASchedStrategy::enterMBB(MachineBasicBlock *NextMBB) {
  79   assert ((SchedStates.find(NextMBB) == SchedStates.end()) &&
  80           "Entering MBB twice?");
  81   LLVM_DEBUG(dbgs() << "** Entering " << printMBBReference(*NextMBB));
  82
  83   MBB = NextMBB;
  84
  85   /// Create a HazardRec for MBB, save it in SchedStates and set HazardRec to
  86   /// point to it.
  87   HazardRec = SchedStates[MBB] = new SystemZHazardRecognizer(TII, &SchedModel);
  88   LLVM_DEBUG(const MachineLoop *Loop = MLI->getLoopFor(MBB);
  89              if (Loop && Loop->getHeader() == MBB) dbgs() << " (Loop header)";
  90              dbgs() << ":\n";);
  91
  92   // Try to take over the state from a single predecessor, if it has been
  93   // scheduled. If this is not possible, we are done.
  94   MachineBasicBlock *SinglePredMBB =
  95     getSingleSchedPred(MBB, MLI->getLoopFor(MBB));
  96   if (SinglePredMBB == nullptr ||
  97       SchedStates.find(SinglePredMBB) == SchedStates.end())
  98     return;
  99
 100   LLVM_DEBUG(dbgs() << "** Continued scheduling from "
 101                     << printMBBReference(*SinglePredMBB) << "\n";);
 102
 103   HazardRec->copyState(SchedStates[SinglePredMBB]);
 104   LLVM_DEBUG(HazardRec->dumpState(););
 105
 106   // Emit incoming terminator(s). Be optimistic and assume that branch
 107   // prediction will generally do "the right thing".
 108   for (MachineBasicBlock::iterator I = SinglePredMBB->getFirstTerminator();
 109        I != SinglePredMBB->end(); I++) {
 110     LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; I->dump(););
 111     bool TakenBranch = (I->isBranch() &&
 112                         (TII->getBranchInfo(*I).isIndirect() ||
 113                          TII->getBranchInfo(*I).getMBBTarget() == MBB));
 114     HazardRec->emitInstruction(&*I, TakenBranch);
 115     if (TakenBranch)
 116       break;
 117   }
 118 }
 119
 120 void SystemZPostRASchedStrategy::leaveMBB() {
 121   LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);
 122
 123   // Advance to first terminator. The successor block will handle terminators
 124   // dependent on CFG layout (T/NT branch etc).
 125   advanceTo(MBB->getFirstTerminator());
 126 }
 127
 128 SystemZPostRASchedStrategy::
 129 SystemZPostRASchedStrategy(const MachineSchedContext *C)
 130   : MLI(C->MLI),
 131     TII(static_cast<const SystemZInstrInfo *>
 132         (C->MF->getSubtarget().getInstrInfo())),
 133     MBB(nullptr), HazardRec(nullptr) {
 134   const TargetSubtargetInfo *ST = &C->MF->getSubtarget();
 135   SchedModel.init(ST);
 136 }
 137
 138 SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {
 139   // Delete hazard recognizers kept around for each MBB.
 140   for (auto I : SchedStates) {
 141     SystemZHazardRecognizer *hazrec = I.second;
 142     delete hazrec;
 143   }
 144 }
 145
 146 void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
 147                                             MachineBasicBlock::iterator End,
 148                                             unsigned NumRegionInstrs) {
 149   // Don't emit the terminators.
 150   if (Begin->isTerminator())
 151     return;
 152
 153   // Emit any instructions before start of region.
 154   advanceTo(Begin);
 155 }
 156
 157 // Pick the next node to schedule.
 158 SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {
 159   // Only scheduling top-down.
 160   IsTopNode = true;
 161
 162   if (Available.empty())
 163     return nullptr;
 164
 165   // If only one choice, return it.
 166   if (Available.size() == 1) {
 167     LLVM_DEBUG(dbgs() << "** Only one: ";
 168                HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);
 169     return *Available.begin();
 170   }
 171
 172   // All nodes that are possible to schedule are stored in the Available set.
 173   LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););
 174
 175   Candidate Best;
 176   for (auto *SU : Available) {
 177
 178     // SU is the next candidate to be compared against current Best.
 179     Candidate c(SU, *HazardRec);
 180
 181     // Remeber which SU is the best candidate.
 182     if (Best.SU == nullptr || c < Best) {
 183       Best = c;
 184       LLVM_DEBUG(dbgs() << "** Best so far: ";);
 185     } else
 186       LLVM_DEBUG(dbgs() << "** Tried      : ";);
 187     LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();
 188                dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);
 189
 190     // Once we know we have seen all SUs that affect grouping or use unbuffered
 191     // resources, we can stop iterating if Best looks good.
 192     if (!SU->isScheduleHigh && Best.noCost())
 193       break;
 194   }
 195
 196   assert (Best.SU != nullptr);
 197   return Best.SU;
 198 }
 199
 200 SystemZPostRASchedStrategy::Candidate::
 201 Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {
 202   SU = SU_;
 203
 204   // Check the grouping cost. For a node that must begin / end a
 205   // group, it is positive if it would do so prematurely, or negative
 206   // if it would fit naturally into the schedule.
 207   GroupingCost = HazardRec.groupingCost(SU);
 208
 209   // Check the resources cost for this SU.
 210   ResourcesCost = HazardRec.resourcesCost(SU);
 211 }
 212
 213 bool SystemZPostRASchedStrategy::Candidate::
 214 operator<(const Candidate &other) {
 215
 216   // Check decoder grouping.
 217   if (GroupingCost < other.GroupingCost)
 218     return true;
 219   if (GroupingCost > other.GroupingCost)
 220     return false;
 221
 222   // Compare the use of resources.
 223   if (ResourcesCost < other.ResourcesCost)
 224     return true;
 225   if (ResourcesCost > other.ResourcesCost)
 226     return false;
 227
 228   // Higher SU is otherwise generally better.
 229   if (SU->getHeight() > other.SU->getHeight())
 230     return true;
 231   if (SU->getHeight() < other.SU->getHeight())
 232     return false;
 233
 234   // If all same, fall back to original order.
 235   if (SU->NodeNum < other.SU->NodeNum)
 236     return true;
 237
 238   return false;
 239 }
 240
 241 void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
 242   LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";
 243              if (Available.size() == 1) dbgs() << "(only one) ";
 244              Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);
 245
 246   // Remove SU from Available set and update HazardRec.
 247   Available.erase(SU);
 248   HazardRec->EmitInstruction(SU);
 249 }
 250
 251 void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {
 252   // Set isScheduleHigh flag on all SUs that we want to consider first in
 253   // pickNode().
 254   const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);
 255   bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));
 256   SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);
 257
 258   // Put all released SUs in the Available set.
 259   Available.insert(SU);
 260 }