263 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// -------------------------- Post RA scheduling ---------------------------- //10// SystemZPostRASchedStrategy is a scheduling strategy which is plugged into11// the MachineScheduler. It has a sorted Available set of SUs and a pickNode()12// implementation that looks to optimize decoder grouping and balance the13// usage of processor resources. Scheduler states are saved for the end14// 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 20using namespace llvm;21 22#define DEBUG_TYPE "machine-scheduler"23 24#ifndef NDEBUG25// Print the set of SUs26void SystemZPostRASchedStrategy::SUSet::27dump(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#endif37 38// Try to find a single predecessor that would be interesting for the39// scheduler in the top-most region of MBB.40static 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 a47 // single block loop.48 if (MBB->pred_size() == 2 && Loop != nullptr && Loop->getHeader() == MBB) {49 for (MachineBasicBlock *Pred : MBB->predecessors())50 if (Loop->contains(Pred))51 PredMBB = (Pred == MBB ? nullptr : Pred);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 60void SystemZPostRASchedStrategy::61advanceTo(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 74void SystemZPostRASchedStrategy::initialize(ScheduleDAGMI *dag) {75 Available.clear(); // -misched-cutoff.76 LLVM_DEBUG(HazardRec->dumpState(););77}78 79void 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 to87 /// 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 been94 // scheduled. If this is not possible, we are done.95 MachineBasicBlock *SinglePredMBB =96 getSingleSchedPred(MBB, MLI->getLoopFor(MBB));97 if (SinglePredMBB == nullptr)98 return;99 auto It = SchedStates.find(SinglePredMBB);100 if (It == SchedStates.end())101 return;102 103 LLVM_DEBUG(dbgs() << "** Continued scheduling from "104 << printMBBReference(*SinglePredMBB) << "\n";);105 106 HazardRec->copyState(It->second);107 LLVM_DEBUG(HazardRec->dumpState(););108 109 // Emit incoming terminator(s). Be optimistic and assume that branch110 // prediction will generally do "the right thing".111 for (MachineInstr &MI : SinglePredMBB->terminators()) {112 LLVM_DEBUG(dbgs() << "** Emitting incoming branch: "; MI.dump(););113 bool TakenBranch = (MI.isBranch() &&114 (TII->getBranchInfo(MI).isIndirect() ||115 TII->getBranchInfo(MI).getMBBTarget() == MBB));116 HazardRec->emitInstruction(&MI, TakenBranch);117 if (TakenBranch)118 break;119 }120}121 122void SystemZPostRASchedStrategy::leaveMBB() {123 LLVM_DEBUG(dbgs() << "** Leaving " << printMBBReference(*MBB) << "\n";);124 125 // Advance to first terminator. The successor block will handle terminators126 // dependent on CFG layout (T/NT branch etc).127 advanceTo(MBB->getFirstTerminator());128}129 130SystemZPostRASchedStrategy::131SystemZPostRASchedStrategy(const MachineSchedContext *C)132 : MLI(C->MLI),133 TII(static_cast<const SystemZInstrInfo *>134 (C->MF->getSubtarget().getInstrInfo())),135 MBB(nullptr), HazardRec(nullptr) {136 const TargetSubtargetInfo *ST = &C->MF->getSubtarget();137 SchedModel.init(ST);138}139 140SystemZPostRASchedStrategy::~SystemZPostRASchedStrategy() {141 // Delete hazard recognizers kept around for each MBB.142 for (auto I : SchedStates) {143 SystemZHazardRecognizer *hazrec = I.second;144 delete hazrec;145 }146}147 148void SystemZPostRASchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,149 MachineBasicBlock::iterator End,150 unsigned NumRegionInstrs) {151 // Don't emit the terminators.152 if (Begin->isTerminator())153 return;154 155 // Emit any instructions before start of region.156 advanceTo(Begin);157}158 159// Pick the next node to schedule.160SUnit *SystemZPostRASchedStrategy::pickNode(bool &IsTopNode) {161 // Only scheduling top-down.162 IsTopNode = true;163 164 if (Available.empty())165 return nullptr;166 167 // If only one choice, return it.168 if (Available.size() == 1) {169 LLVM_DEBUG(dbgs() << "** Only one: ";170 HazardRec->dumpSU(*Available.begin(), dbgs()); dbgs() << "\n";);171 return *Available.begin();172 }173 174 // All nodes that are possible to schedule are stored in the Available set.175 LLVM_DEBUG(dbgs() << "** Available: "; Available.dump(*HazardRec););176 177 Candidate Best;178 for (auto *SU : Available) {179 180 // SU is the next candidate to be compared against current Best.181 Candidate c(SU, *HazardRec);182 183 // Remeber which SU is the best candidate.184 if (Best.SU == nullptr || c < Best) {185 Best = c;186 LLVM_DEBUG(dbgs() << "** Best so far: ";);187 } else188 LLVM_DEBUG(dbgs() << "** Tried : ";);189 LLVM_DEBUG(HazardRec->dumpSU(c.SU, dbgs()); c.dumpCosts();190 dbgs() << " Height:" << c.SU->getHeight(); dbgs() << "\n";);191 192 // Once we know we have seen all SUs that affect grouping or use unbuffered193 // resources, we can stop iterating if Best looks good.194 if (!SU->isScheduleHigh && Best.noCost())195 break;196 }197 198 assert (Best.SU != nullptr);199 return Best.SU;200}201 202SystemZPostRASchedStrategy::Candidate::203Candidate(SUnit *SU_, SystemZHazardRecognizer &HazardRec) : Candidate() {204 SU = SU_;205 206 // Check the grouping cost. For a node that must begin / end a207 // group, it is positive if it would do so prematurely, or negative208 // if it would fit naturally into the schedule.209 GroupingCost = HazardRec.groupingCost(SU);210 211 // Check the resources cost for this SU.212 ResourcesCost = HazardRec.resourcesCost(SU);213}214 215bool SystemZPostRASchedStrategy::Candidate::216operator<(const Candidate &other) {217 218 // Check decoder grouping.219 if (GroupingCost < other.GroupingCost)220 return true;221 if (GroupingCost > other.GroupingCost)222 return false;223 224 // Compare the use of resources.225 if (ResourcesCost < other.ResourcesCost)226 return true;227 if (ResourcesCost > other.ResourcesCost)228 return false;229 230 // Higher SU is otherwise generally better.231 if (SU->getHeight() > other.SU->getHeight())232 return true;233 if (SU->getHeight() < other.SU->getHeight())234 return false;235 236 // If all same, fall back to original order.237 if (SU->NodeNum < other.SU->NodeNum)238 return true;239 240 return false;241}242 243void SystemZPostRASchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {244 LLVM_DEBUG(dbgs() << "** Scheduling SU(" << SU->NodeNum << ") ";245 if (Available.size() == 1) dbgs() << "(only one) ";246 Candidate c(SU, *HazardRec); c.dumpCosts(); dbgs() << "\n";);247 248 // Remove SU from Available set and update HazardRec.249 Available.erase(SU);250 HazardRec->EmitInstruction(SU);251}252 253void SystemZPostRASchedStrategy::releaseTopNode(SUnit *SU) {254 // Set isScheduleHigh flag on all SUs that we want to consider first in255 // pickNode().256 const MCSchedClassDesc *SC = HazardRec->getSchedClass(SU);257 bool AffectsGrouping = (SC->isValid() && (SC->BeginGroup || SC->EndGroup));258 SU->isScheduleHigh = (AffectsGrouping || SU->isUnbuffered);259 260 // Put all released SUs in the Available set.261 Available.insert(SU);262}263