807 lines · cpp
1//===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===//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// This implements a fast scheduler.10//11//===----------------------------------------------------------------------===//12 13#include "InstrEmitter.h"14#include "SDNodeDbgValue.h"15#include "ScheduleDAGSDNodes.h"16#include "llvm/ADT/SmallSet.h"17#include "llvm/ADT/Statistic.h"18#include "llvm/CodeGen/SchedulerRegistry.h"19#include "llvm/CodeGen/SelectionDAGISel.h"20#include "llvm/CodeGen/TargetInstrInfo.h"21#include "llvm/CodeGen/TargetRegisterInfo.h"22#include "llvm/IR/InlineAsm.h"23#include "llvm/Support/Debug.h"24#include "llvm/Support/ErrorHandling.h"25#include "llvm/Support/raw_ostream.h"26using namespace llvm;27 28#define DEBUG_TYPE "pre-RA-sched"29 30STATISTIC(NumUnfolds, "Number of nodes unfolded");31STATISTIC(NumDups, "Number of duplicated nodes");32STATISTIC(NumPRCopies, "Number of physical copies");33 34static RegisterScheduler35 fastDAGScheduler("fast", "Fast suboptimal list scheduling",36 createFastDAGScheduler);37static RegisterScheduler38 linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",39 createDAGLinearizer);40 41 42namespace {43 /// FastPriorityQueue - A degenerate priority queue that considers44 /// all nodes to have the same priority.45 ///46 struct FastPriorityQueue {47 SmallVector<SUnit *, 16> Queue;48 49 bool empty() const { return Queue.empty(); }50 51 void push(SUnit *U) {52 Queue.push_back(U);53 }54 55 SUnit *pop() {56 if (empty()) return nullptr;57 return Queue.pop_back_val();58 }59 };60 61//===----------------------------------------------------------------------===//62/// ScheduleDAGFast - The actual "fast" list scheduler implementation.63///64class ScheduleDAGFast : public ScheduleDAGSDNodes {65private:66 /// AvailableQueue - The priority queue to use for the available SUnits.67 FastPriorityQueue AvailableQueue;68 69 /// LiveRegDefs - A set of physical registers and their definition70 /// that are "live". These nodes must be scheduled before any other nodes that71 /// modifies the registers can be scheduled.72 unsigned NumLiveRegs = 0u;73 std::vector<SUnit*> LiveRegDefs;74 std::vector<unsigned> LiveRegCycles;75 76public:77 ScheduleDAGFast(MachineFunction &mf)78 : ScheduleDAGSDNodes(mf) {}79 80 void Schedule() override;81 82 /// AddPred - adds a predecessor edge to SUnit SU.83 void AddPred(SUnit *SU, const SDep &D) { SU->addPred(D); }84 85 /// RemovePred - removes a predecessor edge from SUnit SU.86 void RemovePred(SUnit *SU, const SDep &D) { SU->removePred(D); }87 88private:89 void ReleasePred(SUnit *SU, SDep *PredEdge);90 void ReleasePredecessors(SUnit *SU, unsigned CurCycle);91 void ScheduleNodeBottomUp(SUnit*, unsigned);92 SUnit *CopyAndMoveSuccessors(SUnit*);93 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,94 const TargetRegisterClass*,95 const TargetRegisterClass*,96 SmallVectorImpl<SUnit*>&);97 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);98 void ListScheduleBottomUp();99 100 /// forceUnitLatencies - The fast scheduler doesn't care about real latencies.101 bool forceUnitLatencies() const override { return true; }102};103} // end anonymous namespace104 105 106/// Schedule - Schedule the DAG using list scheduling.107void ScheduleDAGFast::Schedule() {108 LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");109 110 NumLiveRegs = 0;111 LiveRegDefs.resize(TRI->getNumRegs(), nullptr);112 LiveRegCycles.resize(TRI->getNumRegs(), 0);113 114 // Build the scheduling graph.115 BuildSchedGraph();116 117 LLVM_DEBUG(dump());118 119 // Execute the actual scheduling loop.120 ListScheduleBottomUp();121}122 123//===----------------------------------------------------------------------===//124// Bottom-Up Scheduling125//===----------------------------------------------------------------------===//126 127/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to128/// the AvailableQueue if the count reaches zero. Also update its cycle bound.129void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {130 SUnit *PredSU = PredEdge->getSUnit();131 132#ifndef NDEBUG133 if (PredSU->NumSuccsLeft == 0) {134 dbgs() << "*** Scheduling failed! ***\n";135 dumpNode(*PredSU);136 dbgs() << " has been released too many times!\n";137 llvm_unreachable(nullptr);138 }139#endif140 --PredSU->NumSuccsLeft;141 142 // If all the node's successors are scheduled, this node is ready143 // to be scheduled. Ignore the special EntrySU node.144 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {145 PredSU->isAvailable = true;146 AvailableQueue.push(PredSU);147 }148}149 150void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {151 // Bottom up: release predecessors152 for (SDep &Pred : SU->Preds) {153 ReleasePred(SU, &Pred);154 if (Pred.isAssignedRegDep()) {155 // This is a physical register dependency and it's impossible or156 // expensive to copy the register. Make sure nothing that can157 // clobber the register is scheduled between the predecessor and158 // this node.159 if (!LiveRegDefs[Pred.getReg()]) {160 ++NumLiveRegs;161 LiveRegDefs[Pred.getReg()] = Pred.getSUnit();162 LiveRegCycles[Pred.getReg()] = CurCycle;163 }164 }165 }166}167 168/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending169/// count of its predecessors. If a predecessor pending count is zero, add it to170/// the Available queue.171void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {172 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");173 LLVM_DEBUG(dumpNode(*SU));174 175 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");176 SU->setHeightToAtLeast(CurCycle);177 Sequence.push_back(SU);178 179 ReleasePredecessors(SU, CurCycle);180 181 // Release all the implicit physical register defs that are live.182 for (SDep &Succ : SU->Succs) {183 if (Succ.isAssignedRegDep()) {184 if (LiveRegCycles[Succ.getReg()] == Succ.getSUnit()->getHeight()) {185 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");186 assert(LiveRegDefs[Succ.getReg()] == SU &&187 "Physical register dependency violated?");188 --NumLiveRegs;189 LiveRegDefs[Succ.getReg()] = nullptr;190 LiveRegCycles[Succ.getReg()] = 0;191 }192 }193 }194 195 SU->isScheduled = true;196}197 198/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled199/// successors to the newly created node.200SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {201 if (SU->getNode()->getGluedNode())202 return nullptr;203 204 SDNode *N = SU->getNode();205 if (!N)206 return nullptr;207 208 SUnit *NewSU;209 bool TryUnfold = false;210 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {211 MVT VT = N->getSimpleValueType(i);212 if (VT == MVT::Glue)213 return nullptr;214 else if (VT == MVT::Other)215 TryUnfold = true;216 }217 for (const SDValue &Op : N->op_values()) {218 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());219 if (VT == MVT::Glue)220 return nullptr;221 }222 223 if (TryUnfold) {224 SmallVector<SDNode*, 2> NewNodes;225 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))226 return nullptr;227 228 LLVM_DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");229 assert(NewNodes.size() == 2 && "Expected a load folding node!");230 231 N = NewNodes[1];232 SDNode *LoadNode = NewNodes[0];233 unsigned NumVals = N->getNumValues();234 unsigned OldNumVals = SU->getNode()->getNumValues();235 for (unsigned i = 0; i != NumVals; ++i)236 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));237 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),238 SDValue(LoadNode, 1));239 240 SUnit *NewSU = newSUnit(N);241 assert(N->getNodeId() == -1 && "Node already inserted!");242 N->setNodeId(NewSU->NodeNum);243 244 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());245 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {246 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {247 NewSU->isTwoAddress = true;248 break;249 }250 }251 if (MCID.isCommutable())252 NewSU->isCommutable = true;253 254 // LoadNode may already exist. This can happen when there is another255 // load from the same location and producing the same type of value256 // but it has different alignment or volatileness.257 bool isNewLoad = true;258 SUnit *LoadSU;259 if (LoadNode->getNodeId() != -1) {260 LoadSU = &SUnits[LoadNode->getNodeId()];261 isNewLoad = false;262 } else {263 LoadSU = newSUnit(LoadNode);264 LoadNode->setNodeId(LoadSU->NodeNum);265 }266 267 SDep ChainPred;268 SmallVector<SDep, 4> ChainSuccs;269 SmallVector<SDep, 4> LoadPreds;270 SmallVector<SDep, 4> NodePreds;271 SmallVector<SDep, 4> NodeSuccs;272 for (SDep &Pred : SU->Preds) {273 if (Pred.isCtrl())274 ChainPred = Pred;275 else if (Pred.getSUnit()->getNode() &&276 Pred.getSUnit()->getNode()->isOperandOf(LoadNode))277 LoadPreds.push_back(Pred);278 else279 NodePreds.push_back(Pred);280 }281 for (SDep &Succ : SU->Succs) {282 if (Succ.isCtrl())283 ChainSuccs.push_back(Succ);284 else285 NodeSuccs.push_back(Succ);286 }287 288 if (ChainPred.getSUnit()) {289 RemovePred(SU, ChainPred);290 if (isNewLoad)291 AddPred(LoadSU, ChainPred);292 }293 for (const SDep &Pred : LoadPreds) {294 RemovePred(SU, Pred);295 if (isNewLoad) {296 AddPred(LoadSU, Pred);297 }298 }299 for (const SDep &Pred : NodePreds) {300 RemovePred(SU, Pred);301 AddPred(NewSU, Pred);302 }303 for (SDep D : NodeSuccs) {304 SUnit *SuccDep = D.getSUnit();305 D.setSUnit(SU);306 RemovePred(SuccDep, D);307 D.setSUnit(NewSU);308 AddPred(SuccDep, D);309 }310 for (SDep D : ChainSuccs) {311 SUnit *SuccDep = D.getSUnit();312 D.setSUnit(SU);313 RemovePred(SuccDep, D);314 if (isNewLoad) {315 D.setSUnit(LoadSU);316 AddPred(SuccDep, D);317 }318 }319 if (isNewLoad) {320 SDep D(LoadSU, SDep::Barrier);321 D.setLatency(LoadSU->Latency);322 AddPred(NewSU, D);323 }324 325 ++NumUnfolds;326 327 if (NewSU->NumSuccsLeft == 0) {328 NewSU->isAvailable = true;329 return NewSU;330 }331 SU = NewSU;332 }333 334 LLVM_DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");335 NewSU = Clone(SU);336 337 // New SUnit has the exact same predecessors.338 for (SDep &Pred : SU->Preds)339 if (!Pred.isArtificial())340 AddPred(NewSU, Pred);341 342 // Only copy scheduled successors. Cut them from old node's successor343 // list and move them over.344 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;345 for (SDep &Succ : SU->Succs) {346 if (Succ.isArtificial())347 continue;348 SUnit *SuccSU = Succ.getSUnit();349 if (SuccSU->isScheduled) {350 SDep D = Succ;351 D.setSUnit(NewSU);352 AddPred(SuccSU, D);353 D.setSUnit(SU);354 DelDeps.push_back(std::make_pair(SuccSU, D));355 }356 }357 for (const auto &[Del, Dep] : DelDeps)358 RemovePred(Del, Dep);359 360 ++NumDups;361 return NewSU;362}363 364/// InsertCopiesAndMoveSuccs - Insert register copies and move all365/// scheduled successors of the given SUnit to the last copy.366void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,367 const TargetRegisterClass *DestRC,368 const TargetRegisterClass *SrcRC,369 SmallVectorImpl<SUnit*> &Copies) {370 SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(nullptr));371 CopyFromSU->CopySrcRC = SrcRC;372 CopyFromSU->CopyDstRC = DestRC;373 374 SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(nullptr));375 CopyToSU->CopySrcRC = DestRC;376 CopyToSU->CopyDstRC = SrcRC;377 378 // Only copy scheduled successors. Cut them from old node's successor379 // list and move them over.380 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;381 for (SDep &Succ : SU->Succs) {382 if (Succ.isArtificial())383 continue;384 SUnit *SuccSU = Succ.getSUnit();385 if (SuccSU->isScheduled) {386 SDep D = Succ;387 D.setSUnit(CopyToSU);388 AddPred(SuccSU, D);389 DelDeps.push_back(std::make_pair(SuccSU, Succ));390 }391 }392 for (const auto &[Del, Dep] : DelDeps)393 RemovePred(Del, Dep);394 SDep FromDep(SU, SDep::Data, Reg);395 FromDep.setLatency(SU->Latency);396 AddPred(CopyFromSU, FromDep);397 SDep ToDep(CopyFromSU, SDep::Data, 0);398 ToDep.setLatency(CopyFromSU->Latency);399 AddPred(CopyToSU, ToDep);400 401 Copies.push_back(CopyFromSU);402 Copies.push_back(CopyToSU);403 404 ++NumPRCopies;405}406 407/// getPhysicalRegisterVT - Returns the ValueType of the physical register408/// definition of the specified node.409/// FIXME: Move to SelectionDAG?410static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,411 const TargetInstrInfo *TII) {412 unsigned NumRes;413 if (N->getOpcode() == ISD::CopyFromReg) {414 // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.415 NumRes = 1;416 } else {417 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());418 assert(!MCID.implicit_defs().empty() &&419 "Physical reg def must be in implicit def list!");420 NumRes = MCID.getNumDefs();421 for (MCPhysReg ImpDef : MCID.implicit_defs()) {422 if (Reg == ImpDef)423 break;424 ++NumRes;425 }426 }427 return N->getSimpleValueType(NumRes);428}429 430/// CheckForLiveRegDef - Return true and update live register vector if the431/// specified register def of the specified SUnit clobbers any "live" registers.432static bool CheckForLiveRegDef(SUnit *SU, MCRegister Reg,433 std::vector<SUnit *> &LiveRegDefs,434 SmallSet<unsigned, 4> &RegAdded,435 SmallVectorImpl<unsigned> &LRegs,436 const TargetRegisterInfo *TRI,437 const SDNode *Node = nullptr) {438 bool Added = false;439 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {440 // Check if Ref is live.441 if (!LiveRegDefs[*AI])442 continue;443 444 // Allow multiple uses of the same def.445 if (LiveRegDefs[*AI] == SU)446 continue;447 448 // Allow multiple uses of same def449 if (Node && LiveRegDefs[*AI]->getNode() == Node)450 continue;451 452 // Add Reg to the set of interfering live regs.453 if (RegAdded.insert(*AI).second) {454 LRegs.push_back(*AI);455 Added = true;456 }457 }458 return Added;459}460 461/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay462/// scheduling of the given node to satisfy live physical register dependencies.463/// If the specific node is the last one that's available to schedule, do464/// whatever is necessary (i.e. backtracking or cloning) to make it possible.465bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,466 SmallVectorImpl<unsigned> &LRegs){467 if (NumLiveRegs == 0)468 return false;469 470 SmallSet<unsigned, 4> RegAdded;471 // If this node would clobber any "live" register, then it's not ready.472 for (SDep &Pred : SU->Preds) {473 if (Pred.isAssignedRegDep()) {474 CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs,475 RegAdded, LRegs, TRI);476 }477 }478 479 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {480 if (Node->getOpcode() == ISD::INLINEASM ||481 Node->getOpcode() == ISD::INLINEASM_BR) {482 // Inline asm can clobber physical defs.483 unsigned NumOps = Node->getNumOperands();484 if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)485 --NumOps; // Ignore the glue operand.486 487 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {488 unsigned Flags = Node->getConstantOperandVal(i);489 const InlineAsm::Flag F(Flags);490 unsigned NumVals = F.getNumOperandRegisters();491 492 ++i; // Skip the ID value.493 if (F.isRegDefKind() || F.isRegDefEarlyClobberKind() ||494 F.isClobberKind()) {495 // Check for def of register or earlyclobber register.496 for (; NumVals; --NumVals, ++i) {497 Register Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();498 if (Reg.isPhysical())499 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);500 }501 } else502 i += NumVals;503 }504 continue;505 }506 507 if (Node->getOpcode() == ISD::CopyToReg) {508 Register Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();509 if (Reg.isPhysical()) {510 SDNode *SrcNode = Node->getOperand(2).getNode();511 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI, SrcNode);512 }513 }514 515 if (!Node->isMachineOpcode())516 continue;517 const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());518 for (MCPhysReg Reg : MCID.implicit_defs())519 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);520 }521 return !LRegs.empty();522}523 524 525/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up526/// schedulers.527void ScheduleDAGFast::ListScheduleBottomUp() {528 unsigned CurCycle = 0;529 530 // Release any predecessors of the special Exit node.531 ReleasePredecessors(&ExitSU, CurCycle);532 533 // Add root to Available queue.534 if (!SUnits.empty()) {535 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];536 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");537 RootSU->isAvailable = true;538 AvailableQueue.push(RootSU);539 }540 541 // While Available queue is not empty, grab the node with the highest542 // priority. If it is not ready put it back. Schedule the node.543 SmallVector<SUnit*, 4> NotReady;544 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;545 Sequence.reserve(SUnits.size());546 while (!AvailableQueue.empty()) {547 bool Delayed = false;548 LRegsMap.clear();549 SUnit *CurSU = AvailableQueue.pop();550 while (CurSU) {551 SmallVector<unsigned, 4> LRegs;552 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))553 break;554 Delayed = true;555 LRegsMap.insert(std::make_pair(CurSU, LRegs));556 557 CurSU->isPending = true; // This SU is not in AvailableQueue right now.558 NotReady.push_back(CurSU);559 CurSU = AvailableQueue.pop();560 }561 562 // All candidates are delayed due to live physical reg dependencies.563 // Try code duplication or inserting cross class copies564 // to resolve it.565 if (Delayed && !CurSU) {566 if (!CurSU) {567 // Try duplicating the nodes that produces these568 // "expensive to copy" values to break the dependency. In case even569 // that doesn't work, insert cross class copies.570 SUnit *TrySU = NotReady[0];571 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];572 assert(LRegs.size() == 1 && "Can't handle this yet!");573 unsigned Reg = LRegs[0];574 SUnit *LRDef = LiveRegDefs[Reg];575 MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);576 const TargetRegisterClass *RC =577 TRI->getMinimalPhysRegClass(Reg, VT);578 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);579 580 // If cross copy register class is the same as RC, then it must be581 // possible copy the value directly. Do not try duplicate the def.582 // If cross copy register class is not the same as RC, then it's583 // possible to copy the value but it require cross register class copies584 // and it is expensive.585 // If cross copy register class is null, then it's not possible to copy586 // the value at all.587 SUnit *NewDef = nullptr;588 if (DestRC != RC) {589 NewDef = CopyAndMoveSuccessors(LRDef);590 if (!DestRC && !NewDef)591 report_fatal_error("Can't handle live physical "592 "register dependency!");593 }594 if (!NewDef) {595 // Issue copies, these can be expensive cross register class copies.596 SmallVector<SUnit*, 2> Copies;597 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);598 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum599 << " to SU #" << Copies.front()->NodeNum << "\n");600 AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));601 NewDef = Copies.back();602 }603 604 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum605 << " to SU #" << TrySU->NodeNum << "\n");606 LiveRegDefs[Reg] = NewDef;607 AddPred(NewDef, SDep(TrySU, SDep::Artificial));608 TrySU->isAvailable = false;609 CurSU = NewDef;610 }611 612 if (!CurSU) {613 llvm_unreachable("Unable to resolve live physical register dependencies!");614 }615 }616 617 // Add the nodes that aren't ready back onto the available list.618 for (SUnit *SU : NotReady) {619 SU->isPending = false;620 // May no longer be available due to backtracking.621 if (SU->isAvailable)622 AvailableQueue.push(SU);623 }624 NotReady.clear();625 626 if (CurSU)627 ScheduleNodeBottomUp(CurSU, CurCycle);628 ++CurCycle;629 }630 631 // Reverse the order since it is bottom up.632 std::reverse(Sequence.begin(), Sequence.end());633 634#ifndef NDEBUG635 VerifyScheduledSequence(/*isBottomUp=*/true);636#endif637}638 639 640namespace {641//===----------------------------------------------------------------------===//642// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the643// DAG in topological order.644// IMPORTANT: this may not work for targets with phyreg dependency.645//646class ScheduleDAGLinearize : public ScheduleDAGSDNodes {647public:648 ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}649 650 void Schedule() override;651 652 MachineBasicBlock *653 EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;654 655private:656 std::vector<SDNode*> Sequence;657 DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user658 659 void ScheduleNode(SDNode *N);660};661} // end anonymous namespace662 663void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {664 if (N->getNodeId() != 0)665 llvm_unreachable(nullptr);666 667 if (!N->isMachineOpcode() &&668 (N->getOpcode() == ISD::EntryToken || isPassiveNode(N)))669 // These nodes do not need to be translated into MIs.670 return;671 672 LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");673 LLVM_DEBUG(N->dump(DAG));674 Sequence.push_back(N);675 676 unsigned NumOps = N->getNumOperands();677 if (unsigned NumLeft = NumOps) {678 SDNode *GluedOpN = nullptr;679 do {680 const SDValue &Op = N->getOperand(NumLeft-1);681 SDNode *OpN = Op.getNode();682 683 if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) {684 // Schedule glue operand right above N.685 GluedOpN = OpN;686 assert(OpN->getNodeId() != 0 && "Glue operand not ready?");687 OpN->setNodeId(0);688 ScheduleNode(OpN);689 continue;690 }691 692 if (OpN == GluedOpN)693 // Glue operand is already scheduled.694 continue;695 696 DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN);697 if (DI != GluedMap.end() && DI->second != N)698 // Users of glues are counted against the glued users.699 OpN = DI->second;700 701 unsigned Degree = OpN->getNodeId();702 assert(Degree > 0 && "Predecessor over-released!");703 OpN->setNodeId(--Degree);704 if (Degree == 0)705 ScheduleNode(OpN);706 } while (--NumLeft);707 }708}709 710/// findGluedUser - Find the representative use of a glue value by walking711/// the use chain.712static SDNode *findGluedUser(SDNode *N) {713 while (SDNode *Glued = N->getGluedUser())714 N = Glued;715 return N;716}717 718void ScheduleDAGLinearize::Schedule() {719 LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");720 721 SmallVector<SDNode*, 8> Glues;722 unsigned DAGSize = 0;723 for (SDNode &Node : DAG->allnodes()) {724 SDNode *N = &Node;725 726 // Use node id to record degree.727 unsigned Degree = N->use_size();728 N->setNodeId(Degree);729 unsigned NumVals = N->getNumValues();730 if (NumVals && N->getValueType(NumVals-1) == MVT::Glue &&731 N->hasAnyUseOfValue(NumVals-1)) {732 SDNode *User = findGluedUser(N);733 if (User) {734 Glues.push_back(N);735 GluedMap.insert(std::make_pair(N, User));736 }737 }738 739 if (N->isMachineOpcode() ||740 (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N)))741 ++DAGSize;742 }743 744 for (SDNode *Glue : Glues) {745 SDNode *GUser = GluedMap[Glue];746 unsigned Degree = Glue->getNodeId();747 unsigned UDegree = GUser->getNodeId();748 749 // Glue user must be scheduled together with the glue operand. So other750 // users of the glue operand must be treated as its users.751 SDNode *ImmGUser = Glue->getGluedUser();752 for (const SDNode *U : Glue->users())753 if (U == ImmGUser)754 --Degree;755 GUser->setNodeId(UDegree + Degree);756 Glue->setNodeId(1);757 }758 759 Sequence.reserve(DAGSize);760 ScheduleNode(DAG->getRoot().getNode());761}762 763MachineBasicBlock*764ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {765 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);766 InstrEmitter::VRBaseMapType VRBaseMap;767 768 LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });769 770 unsigned NumNodes = Sequence.size();771 MachineBasicBlock *BB = Emitter.getBlock();772 for (unsigned i = 0; i != NumNodes; ++i) {773 SDNode *N = Sequence[NumNodes-i-1];774 LLVM_DEBUG(N->dump(DAG));775 Emitter.EmitNode(N, false, false, VRBaseMap);776 777 // Emit any debug values associated with the node.778 if (N->getHasDebugValue()) {779 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();780 for (auto *DV : DAG->GetDbgValues(N)) {781 if (!DV->isEmitted())782 if (auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap))783 BB->insert(InsertPos, DbgMI);784 }785 }786 }787 788 LLVM_DEBUG(dbgs() << '\n');789 790 InsertPos = Emitter.getInsertPos();791 return Emitter.getBlock();792}793 794//===----------------------------------------------------------------------===//795// Public Constructor Functions796//===----------------------------------------------------------------------===//797 798llvm::ScheduleDAGSDNodes *llvm::createFastDAGScheduler(SelectionDAGISel *IS,799 CodeGenOptLevel) {800 return new ScheduleDAGFast(*IS->MF);801}802 803llvm::ScheduleDAGSDNodes *llvm::createDAGLinearizer(SelectionDAGISel *IS,804 CodeGenOptLevel) {805 return new ScheduleDAGLinearize(*IS->MF);806}807