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