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