1097 lines · cpp
1//===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//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 the ScheduleDAG class, which is a base class used by10// scheduling implementation classes.11//12//===----------------------------------------------------------------------===//13 14#include "ScheduleDAGSDNodes.h"15#include "InstrEmitter.h"16#include "SDNodeDbgValue.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/SmallPtrSet.h"19#include "llvm/ADT/SmallSet.h"20#include "llvm/ADT/SmallVector.h"21#include "llvm/ADT/Statistic.h"22#include "llvm/CodeGen/MachineInstrBuilder.h"23#include "llvm/CodeGen/MachineRegisterInfo.h"24#include "llvm/CodeGen/SelectionDAG.h"25#include "llvm/CodeGen/TargetInstrInfo.h"26#include "llvm/CodeGen/TargetLowering.h"27#include "llvm/CodeGen/TargetRegisterInfo.h"28#include "llvm/CodeGen/TargetSubtargetInfo.h"29#include "llvm/Config/llvm-config.h"30#include "llvm/IR/MemoryModelRelaxationAnnotations.h"31#include "llvm/MC/MCInstrItineraries.h"32#include "llvm/Support/CommandLine.h"33#include "llvm/Support/Debug.h"34#include "llvm/Support/raw_ostream.h"35#include "llvm/Target/TargetMachine.h"36using namespace llvm;37 38#define DEBUG_TYPE "pre-RA-sched"39 40STATISTIC(LoadsClustered, "Number of loads clustered together");41 42// This allows the latency-based scheduler to notice high latency instructions43// without a target itinerary. The choice of number here has more to do with44// balancing scheduler heuristics than with the actual machine latency.45static cl::opt<int> HighLatencyCycles(46 "sched-high-latency-cycles", cl::Hidden, cl::init(10),47 cl::desc("Roughly estimate the number of cycles that 'long latency' "48 "instructions take for targets with no itinerary"));49 50ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf)51 : ScheduleDAG(mf), InstrItins(mf.getSubtarget().getInstrItineraryData()) {}52 53/// Run - perform scheduling.54///55void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) {56 BB = bb;57 DAG = dag;58 59 // Clear the scheduler's SUnit DAG.60 ScheduleDAG::clearDAG();61 Sequence.clear();62 63 // Invoke the target's selection of scheduler.64 Schedule();65}66 67/// NewSUnit - Creates a new SUnit and return a ptr to it.68///69SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) {70#ifndef NDEBUG71 const SUnit *Addr = nullptr;72 if (!SUnits.empty())73 Addr = &SUnits[0];74#endif75 SUnits.emplace_back(N, (unsigned)SUnits.size());76 assert((Addr == nullptr || Addr == &SUnits[0]) &&77 "SUnits std::vector reallocated on the fly!");78 SUnits.back().OrigNode = &SUnits.back();79 SUnit *SU = &SUnits.back();80 const TargetLowering &TLI = DAG->getTargetLoweringInfo();81 if (!N ||82 (N->isMachineOpcode() &&83 N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))84 SU->SchedulingPref = Sched::None;85 else86 SU->SchedulingPref = TLI.getSchedulingPreference(N);87 return SU;88}89 90SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {91 SUnit *SU = newSUnit(Old->getNode());92 SU->OrigNode = Old->OrigNode;93 SU->Latency = Old->Latency;94 SU->isVRegCycle = Old->isVRegCycle;95 SU->isCall = Old->isCall;96 SU->isCallOp = Old->isCallOp;97 SU->isTwoAddress = Old->isTwoAddress;98 SU->isCommutable = Old->isCommutable;99 SU->hasPhysRegDefs = Old->hasPhysRegDefs;100 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers;101 SU->isScheduleHigh = Old->isScheduleHigh;102 SU->isScheduleLow = Old->isScheduleLow;103 SU->SchedulingPref = Old->SchedulingPref;104 Old->isCloned = true;105 return SU;106}107 108/// CheckForPhysRegDependency - Check if the dependency between def and use of109/// a specified operand is a physical register dependency. If so, returns the110/// register and the cost of copying the register.111static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,112 const TargetRegisterInfo *TRI,113 const TargetInstrInfo *TII,114 MCRegister &PhysReg, int &Cost) {115 if (Op != 2 || User->getOpcode() != ISD::CopyToReg)116 return;117 118 Register Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();119 if (Reg.isVirtual())120 return;121 122 unsigned ResNo = User->getOperand(2).getResNo();123 if (Def->getOpcode() == ISD::CopyFromReg &&124 cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {125 PhysReg = Reg;126 } else if (Def->isMachineOpcode()) {127 const MCInstrDesc &II = TII->get(Def->getMachineOpcode());128 if (ResNo >= II.getNumDefs() && II.hasImplicitDefOfPhysReg(Reg))129 PhysReg = Reg;130 }131 132 if (PhysReg) {133 const TargetRegisterClass *RC =134 TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));135 Cost = RC->expensiveOrImpossibleToCopy() ? -1 : RC->getCopyCost();136 }137}138 139// Helper for AddGlue to clone node operands.140static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef<EVT> VTs,141 SDValue ExtraOper = SDValue()) {142 SmallVector<SDValue, 8> Ops(N->ops());143 if (ExtraOper.getNode())144 Ops.push_back(ExtraOper);145 146 SDVTList VTList = DAG->getVTList(VTs);147 MachineSDNode *MN = dyn_cast<MachineSDNode>(N);148 149 // Store memory references.150 SmallVector<MachineMemOperand *, 2> MMOs;151 if (MN)152 MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());153 154 DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);155 156 // Reset the memory references157 if (MN)158 DAG->setNodeMemRefs(MN, MMOs);159}160 161static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {162 SDNode *GlueDestNode = Glue.getNode();163 164 // Don't add glue from a node to itself.165 if (GlueDestNode == N) return false;166 167 // Don't add a glue operand to something that already uses glue.168 if (GlueDestNode &&169 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {170 return false;171 }172 // Don't add glue to something that already has a glue value.173 if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;174 175 SmallVector<EVT, 4> VTs(N->values());176 if (AddGlue)177 VTs.push_back(MVT::Glue);178 179 CloneNodeWithValues(N, DAG, VTs, Glue);180 181 return true;182}183 184// Cleanup after unsuccessful AddGlue. Use the standard method of morphing the185// node even though simply shrinking the value list is sufficient.186static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) {187 assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&188 !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&189 "expected an unused glue value");190 191 CloneNodeWithValues(N, DAG,192 ArrayRef(N->value_begin(), N->getNumValues() - 1));193}194 195/// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.196/// This function finds loads of the same base and different offsets. If the197/// offsets are not far apart (target specific), it add MVT::Glue inputs and198/// outputs to ensure they are scheduled together and in order. This199/// optimization may benefit some targets by improving cache locality.200void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {201 SDValue Chain;202 unsigned NumOps = Node->getNumOperands();203 if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)204 Chain = Node->getOperand(NumOps-1);205 if (!Chain)206 return;207 208 // Skip any load instruction that has a tied input. There may be an additional209 // dependency requiring a different order than by increasing offsets, and the210 // added glue may introduce a cycle.211 auto hasTiedInput = [this](const SDNode *N) {212 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());213 for (unsigned I = 0; I != MCID.getNumOperands(); ++I) {214 if (MCID.getOperandConstraint(I, MCOI::TIED_TO) != -1)215 return true;216 }217 218 return false;219 };220 221 // Look for other loads of the same chain. Find loads that are loading from222 // the same base pointer and different offsets.223 SmallPtrSet<SDNode*, 16> Visited;224 SmallVector<int64_t, 4> Offsets;225 DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode.226 bool Cluster = false;227 SDNode *Base = Node;228 229 if (hasTiedInput(Base))230 return;231 232 // This algorithm requires a reasonably low use count before finding a match233 // to avoid uselessly blowing up compile time in large blocks.234 unsigned UseCount = 0;235 for (SDNode::user_iterator I = Chain->user_begin(), E = Chain->user_end();236 I != E && UseCount < 100; ++I, ++UseCount) {237 if (I.getUse().getResNo() != Chain.getResNo())238 continue;239 240 SDNode *User = *I;241 if (User == Node || !Visited.insert(User).second)242 continue;243 int64_t Offset1, Offset2;244 if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||245 Offset1 == Offset2 ||246 hasTiedInput(User)) {247 // FIXME: Should be ok if they addresses are identical. But earlier248 // optimizations really should have eliminated one of the loads.249 continue;250 }251 if (O2SMap.insert(std::make_pair(Offset1, Base)).second)252 Offsets.push_back(Offset1);253 O2SMap.insert(std::make_pair(Offset2, User));254 Offsets.push_back(Offset2);255 if (Offset2 < Offset1)256 Base = User;257 Cluster = true;258 // Reset UseCount to allow more matches.259 UseCount = 0;260 }261 262 if (!Cluster)263 return;264 265 // Sort them in increasing order.266 llvm::sort(Offsets);267 268 // Check if the loads are close enough.269 SmallVector<SDNode*, 4> Loads;270 unsigned NumLoads = 0;271 int64_t BaseOff = Offsets[0];272 SDNode *BaseLoad = O2SMap[BaseOff];273 Loads.push_back(BaseLoad);274 for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {275 int64_t Offset = Offsets[i];276 SDNode *Load = O2SMap[Offset];277 if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))278 break; // Stop right here. Ignore loads that are further away.279 Loads.push_back(Load);280 ++NumLoads;281 }282 283 if (NumLoads == 0)284 return;285 286 // Cluster loads by adding MVT::Glue outputs and inputs. This also287 // ensure they are scheduled in order of increasing addresses.288 SDNode *Lead = Loads[0];289 SDValue InGlue;290 if (AddGlue(Lead, InGlue, true, DAG))291 InGlue = SDValue(Lead, Lead->getNumValues() - 1);292 for (unsigned I = 1, E = Loads.size(); I != E; ++I) {293 bool OutGlue = I < E - 1;294 SDNode *Load = Loads[I];295 296 // If AddGlue fails, we could leave an unsused glue value. This should not297 // cause any298 if (AddGlue(Load, InGlue, OutGlue, DAG)) {299 if (OutGlue)300 InGlue = SDValue(Load, Load->getNumValues() - 1);301 302 ++LoadsClustered;303 }304 else if (!OutGlue && InGlue.getNode())305 RemoveUnusedGlue(InGlue.getNode(), DAG);306 }307}308 309/// ClusterNodes - Cluster certain nodes which should be scheduled together.310///311void ScheduleDAGSDNodes::ClusterNodes() {312 for (SDNode &NI : DAG->allnodes()) {313 SDNode *Node = &NI;314 if (!Node || !Node->isMachineOpcode())315 continue;316 317 unsigned Opc = Node->getMachineOpcode();318 const MCInstrDesc &MCID = TII->get(Opc);319 if (MCID.mayLoad())320 // Cluster loads from "near" addresses into combined SUnits.321 ClusterNeighboringLoads(Node);322 }323}324 325void ScheduleDAGSDNodes::BuildSchedUnits() {326 // During scheduling, the NodeId field of SDNode is used to map SDNodes327 // to their associated SUnits by holding SUnits table indices. A value328 // of -1 means the SDNode does not yet have an associated SUnit.329 unsigned NumNodes = 0;330 for (SDNode &NI : DAG->allnodes()) {331 NI.setNodeId(-1);332 ++NumNodes;333 }334 335 // Reserve entries in the vector for each of the SUnits we are creating. This336 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get337 // invalidated.338 // FIXME: Multiply by 2 because we may clone nodes during scheduling.339 // This is a temporary workaround.340 SUnits.reserve(NumNodes * 2);341 342 // Add all nodes in depth first order.343 SmallVector<SDNode*, 64> Worklist;344 SmallPtrSet<SDNode*, 32> Visited;345 Worklist.push_back(DAG->getRoot().getNode());346 Visited.insert(DAG->getRoot().getNode());347 348 SmallVector<SUnit*, 8> CallSUnits;349 while (!Worklist.empty()) {350 SDNode *NI = Worklist.pop_back_val();351 352 // Add all operands to the worklist unless they've already been added.353 for (const SDValue &Op : NI->op_values())354 if (Visited.insert(Op.getNode()).second)355 Worklist.push_back(Op.getNode());356 357 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.358 continue;359 360 // If this node has already been processed, stop now.361 if (NI->getNodeId() != -1) continue;362 363 SUnit *NodeSUnit = newSUnit(NI);364 365 // See if anything is glued to this node, if so, add them to glued366 // nodes. Nodes can have at most one glue input and one glue output. Glue367 // is required to be the last operand and result of a node.368 369 // Scan up to find glued preds.370 SDNode *N = NI;371 while (N->getNumOperands() &&372 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {373 N = N->getOperand(N->getNumOperands()-1).getNode();374 assert(N->getNodeId() == -1 && "Node already inserted!");375 N->setNodeId(NodeSUnit->NodeNum);376 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())377 NodeSUnit->isCall = true;378 }379 380 // Scan down to find any glued succs.381 N = NI;382 while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {383 SDValue GlueVal(N, N->getNumValues()-1);384 385 // There are either zero or one users of the Glue result.386 bool HasGlueUse = false;387 for (SDNode *U : N->users())388 if (GlueVal.isOperandOf(U)) {389 HasGlueUse = true;390 assert(N->getNodeId() == -1 && "Node already inserted!");391 N->setNodeId(NodeSUnit->NodeNum);392 N = U;393 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())394 NodeSUnit->isCall = true;395 break;396 }397 if (!HasGlueUse) break;398 }399 400 if (NodeSUnit->isCall)401 CallSUnits.push_back(NodeSUnit);402 403 // Schedule zero-latency TokenFactor below any nodes that may increase the404 // schedule height. Otherwise, ancestors of the TokenFactor may appear to405 // have false stalls.406 if (NI->getOpcode() == ISD::TokenFactor)407 NodeSUnit->isScheduleLow = true;408 409 // If there are glue operands involved, N is now the bottom-most node410 // of the sequence of nodes that are glued together.411 // Update the SUnit.412 NodeSUnit->setNode(N);413 assert(N->getNodeId() == -1 && "Node already inserted!");414 N->setNodeId(NodeSUnit->NodeNum);415 416 // Compute NumRegDefsLeft. This must be done before AddSchedEdges.417 InitNumRegDefsLeft(NodeSUnit);418 419 // Assign the Latency field of NodeSUnit using target-provided information.420 computeLatency(NodeSUnit);421 }422 423 // Find all call operands.424 while (!CallSUnits.empty()) {425 SUnit *SU = CallSUnits.pop_back_val();426 for (const SDNode *SUNode = SU->getNode(); SUNode;427 SUNode = SUNode->getGluedNode()) {428 if (SUNode->getOpcode() != ISD::CopyToReg)429 continue;430 SDNode *SrcN = SUNode->getOperand(2).getNode();431 if (isPassiveNode(SrcN)) continue; // Not scheduled.432 SUnit *SrcSU = &SUnits[SrcN->getNodeId()];433 SrcSU->isCallOp = true;434 }435 }436}437 438void ScheduleDAGSDNodes::AddSchedEdges() {439 const TargetSubtargetInfo &ST = MF.getSubtarget();440 441 // Check to see if the scheduler cares about latencies.442 bool UnitLatencies = forceUnitLatencies();443 444 // Pass 2: add the preds, succs, etc.445 for (SUnit &SU : SUnits) {446 SDNode *MainNode = SU.getNode();447 448 if (MainNode->isMachineOpcode()) {449 unsigned Opc = MainNode->getMachineOpcode();450 const MCInstrDesc &MCID = TII->get(Opc);451 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {452 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {453 SU.isTwoAddress = true;454 break;455 }456 }457 if (MCID.isCommutable())458 SU.isCommutable = true;459 }460 461 // Find all predecessors and successors of the group.462 for (SDNode *N = SU.getNode(); N; N = N->getGluedNode()) {463 if (N->isMachineOpcode() &&464 !TII->get(N->getMachineOpcode()).implicit_defs().empty()) {465 SU.hasPhysRegClobbers = true;466 unsigned NumUsed = InstrEmitter::CountResults(N);467 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))468 --NumUsed; // Skip over unused values at the end.469 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())470 SU.hasPhysRegDefs = true;471 }472 473 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {474 SDNode *OpN = N->getOperand(i).getNode();475 unsigned DefIdx = N->getOperand(i).getResNo();476 if (isPassiveNode(OpN)) continue; // Not scheduled.477 SUnit *OpSU = &SUnits[OpN->getNodeId()];478 assert(OpSU && "Node has no SUnit!");479 if (OpSU == &SU)480 continue; // In the same group.481 482 EVT OpVT = N->getOperand(i).getValueType();483 assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");484 bool isChain = OpVT == MVT::Other;485 486 MCRegister PhysReg;487 int Cost = 1;488 // Determine if this is a physical register dependency.489 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);490 assert((!PhysReg || !isChain) && "Chain dependence via physreg data?");491 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler492 // emits a copy from the physical register to a virtual register unless493 // it requires a cross class copy (cost < 0). That means we are only494 // treating "expensive to copy" register dependency as physical register495 // dependency. This may change in the future though.496 if (Cost >= 0 && !StressSched)497 PhysReg = MCRegister();498 499 // If this is a ctrl dep, latency is 1.500 unsigned OpLatency = isChain ? 1 : OpSU->Latency;501 // Special-case TokenFactor chains as zero-latency.502 if(isChain && OpN->getOpcode() == ISD::TokenFactor)503 OpLatency = 0;504 505 SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)506 : SDep(OpSU, SDep::Data, PhysReg);507 Dep.setLatency(OpLatency);508 if (!isChain && !UnitLatencies) {509 computeOperandLatency(OpN, N, i, Dep);510 ST.adjustSchedDependency(OpSU, DefIdx, &SU, i, Dep, nullptr);511 }512 513 if (!SU.addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {514 // Multiple register uses are combined in the same SUnit. For example,515 // we could have a set of glued nodes with all their defs consumed by516 // another set of glued nodes. Register pressure tracking sees this as517 // a single use, so to keep pressure balanced we reduce the defs.518 //519 // We can't tell (without more book-keeping) if this results from520 // glued nodes or duplicate operands. As long as we don't reduce521 // NumRegDefsLeft to zero, we handle the common cases well.522 --OpSU->NumRegDefsLeft;523 }524 }525 }526 }527}528 529/// BuildSchedGraph - Build the SUnit graph from the selection dag that we530/// are input. This SUnit graph is similar to the SelectionDAG, but531/// excludes nodes that aren't interesting to scheduling, and represents532/// glued together nodes with a single SUnit.533void ScheduleDAGSDNodes::BuildSchedGraph() {534 // Cluster certain nodes which should be scheduled together.535 ClusterNodes();536 // Populate the SUnits array.537 BuildSchedUnits();538 // Compute all the scheduling dependencies between nodes.539 AddSchedEdges();540}541 542// Initialize NumNodeDefs for the current Node's opcode.543void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {544 // Check for phys reg copy.545 if (!Node)546 return;547 548 if (!Node->isMachineOpcode()) {549 if (Node->getOpcode() == ISD::CopyFromReg)550 NodeNumDefs = 1;551 else552 NodeNumDefs = 0;553 return;554 }555 unsigned POpc = Node->getMachineOpcode();556 if (POpc == TargetOpcode::IMPLICIT_DEF) {557 // No register need be allocated for this.558 NodeNumDefs = 0;559 return;560 }561 if (POpc == TargetOpcode::PATCHPOINT &&562 Node->getValueType(0) == MVT::Other) {563 // PATCHPOINT is defined to have one result, but it might really have none564 // if we're not using CallingConv::AnyReg. Don't mistake the chain for a565 // real definition.566 NodeNumDefs = 0;567 return;568 }569 unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();570 // Some instructions define regs that are not represented in the selection DAG571 // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.572 NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);573 DefIdx = 0;574}575 576// Construct a RegDefIter for this SUnit and find the first valid value.577ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU,578 const ScheduleDAGSDNodes *SD)579 : SchedDAG(SD), Node(SU->getNode()) {580 InitNodeNumDefs();581 Advance();582}583 584// Advance to the next valid value defined by the SUnit.585void ScheduleDAGSDNodes::RegDefIter::Advance() {586 for (;Node;) { // Visit all glued nodes.587 for (;DefIdx < NodeNumDefs; ++DefIdx) {588 if (!Node->hasAnyUseOfValue(DefIdx))589 continue;590 ValueType = Node->getSimpleValueType(DefIdx);591 ++DefIdx;592 return; // Found a normal regdef.593 }594 Node = Node->getGluedNode();595 if (!Node) {596 return; // No values left to visit.597 }598 InitNodeNumDefs();599 }600}601 602void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) {603 assert(SU->NumRegDefsLeft == 0 && "expect a new node");604 for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {605 assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");606 ++SU->NumRegDefsLeft;607 }608}609 610void ScheduleDAGSDNodes::computeLatency(SUnit *SU) {611 SDNode *N = SU->getNode();612 613 // TokenFactor operands are considered zero latency, and some schedulers614 // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero615 // whenever node latency is nonzero.616 if (N && N->getOpcode() == ISD::TokenFactor) {617 SU->Latency = 0;618 return;619 }620 621 // Check to see if the scheduler cares about latencies.622 if (forceUnitLatencies()) {623 SU->Latency = 1;624 return;625 }626 627 if (!InstrItins || InstrItins->isEmpty()) {628 if (N && N->isMachineOpcode() &&629 TII->isHighLatencyDef(N->getMachineOpcode()))630 SU->Latency = HighLatencyCycles;631 else632 SU->Latency = 1;633 return;634 }635 636 // Compute the latency for the node. We use the sum of the latencies for637 // all nodes glued together into this SUnit.638 SU->Latency = 0;639 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())640 if (N->isMachineOpcode())641 SU->Latency += TII->getInstrLatency(InstrItins, N);642}643 644void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use,645 unsigned OpIdx, SDep& dep) const{646 // Check to see if the scheduler cares about latencies.647 if (forceUnitLatencies())648 return;649 650 if (dep.getKind() != SDep::Data)651 return;652 653 unsigned DefIdx = Use->getOperand(OpIdx).getResNo();654 if (Use->isMachineOpcode())655 // Adjust the use operand index by num of defs.656 OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();657 std::optional<unsigned> Latency =658 TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);659 if (Latency > 1U && Use->getOpcode() == ISD::CopyToReg &&660 !BB->succ_empty()) {661 Register Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();662 if (Reg.isVirtual())663 // This copy is a liveout value. It is likely coalesced, so reduce the664 // latency so not to penalize the def.665 // FIXME: need target specific adjustment here?666 Latency = *Latency - 1;667 }668 if (Latency)669 dep.setLatency(*Latency);670}671 672void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {673#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)674 dumpNodeName(SU);675 dbgs() << ": ";676 677 if (!SU.getNode()) {678 dbgs() << "PHYS REG COPY\n";679 return;680 }681 682 SU.getNode()->dump(DAG);683 dbgs() << "\n";684 SmallVector<SDNode *, 4> GluedNodes;685 for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())686 GluedNodes.push_back(N);687 while (!GluedNodes.empty()) {688 dbgs() << " ";689 GluedNodes.back()->dump(DAG);690 dbgs() << "\n";691 GluedNodes.pop_back();692 }693#endif694}695 696void ScheduleDAGSDNodes::dump() const {697#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)698 if (EntrySU.getNode() != nullptr)699 dumpNodeAll(EntrySU);700 for (const SUnit &SU : SUnits)701 dumpNodeAll(SU);702 if (ExitSU.getNode() != nullptr)703 dumpNodeAll(ExitSU);704#endif705}706 707#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)708void ScheduleDAGSDNodes::dumpSchedule() const {709 for (const SUnit *SU : Sequence) {710 if (SU)711 dumpNode(*SU);712 else713 dbgs() << "**** NOOP ****\n";714 }715}716#endif717 718#ifndef NDEBUG719/// VerifyScheduledSequence - Verify that all SUnits were scheduled and that720/// their state is consistent with the nodes listed in Sequence.721///722void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) {723 unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);724 unsigned Noops = llvm::count(Sequence, nullptr);725 assert(Sequence.size() - Noops == ScheduledNodes &&726 "The number of nodes scheduled doesn't match the expected number!");727}728#endif // NDEBUG729 730/// ProcessSDDbgValues - Process SDDbgValues associated with this node.731static void732ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,733 SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,734 InstrEmitter::VRBaseMapType &VRBaseMap, unsigned Order) {735 if (!N->getHasDebugValue())736 return;737 738 /// Returns true if \p DV has any VReg operand locations which don't exist in739 /// VRBaseMap.740 auto HasUnknownVReg = [&VRBaseMap](SDDbgValue *DV) {741 for (const SDDbgOperand &L : DV->getLocationOps()) {742 if (L.getKind() == SDDbgOperand::SDNODE &&743 VRBaseMap.count({L.getSDNode(), L.getResNo()}) == 0)744 return true;745 }746 return false;747 };748 749 // Opportunistically insert immediate dbg_value uses, i.e. those with the same750 // source order number as N.751 MachineBasicBlock *BB = Emitter.getBlock();752 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();753 for (auto *DV : DAG->GetDbgValues(N)) {754 if (DV->isEmitted())755 continue;756 unsigned DVOrder = DV->getOrder();757 if (Order != 0 && DVOrder != Order)758 continue;759 // If DV has any VReg location operands which haven't been mapped then760 // either that node is no longer available or we just haven't visited the761 // node yet. In the former case we should emit an undef dbg_value, but we762 // can do it later. And for the latter we'll want to wait until all763 // dependent nodes have been visited.764 if (!DV->isInvalidated() && HasUnknownVReg(DV))765 continue;766 MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);767 if (!DbgMI)768 continue;769 Orders.push_back({DVOrder, DbgMI});770 BB->insert(InsertPos, DbgMI);771 }772}773 774// ProcessSourceNode - Process nodes with source order numbers. These are added775// to a vector which EmitSchedule uses to determine how to insert dbg_value776// instructions in the right order.777static void778ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,779 InstrEmitter::VRBaseMapType &VRBaseMap,780 SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,781 SmallSet<Register, 8> &Seen, MachineInstr *NewInsn) {782 unsigned Order = N->getIROrder();783 if (!Order || Seen.count(Order)) {784 // Process any valid SDDbgValues even if node does not have any order785 // assigned.786 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);787 return;788 }789 790 // If a new instruction was generated for this Order number, record it.791 // Otherwise, leave this order number unseen: we will either find later792 // instructions for it, or leave it unseen if there were no instructions at793 // all.794 if (NewInsn) {795 Seen.insert(Order);796 Orders.push_back({Order, NewInsn});797 }798 799 // Even if no instruction was generated, a Value may have become defined via800 // earlier nodes. Try to process them now.801 ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);802}803 804void ScheduleDAGSDNodes::805EmitPhysRegCopy(SUnit *SU, SmallDenseMap<SUnit *, Register, 16> &VRBaseMap,806 MachineBasicBlock::iterator InsertPos) {807 for (const SDep &Pred : SU->Preds) {808 if (Pred.isCtrl())809 continue; // ignore chain preds810 if (Pred.getSUnit()->CopyDstRC) {811 // Copy to physical register.812 DenseMap<SUnit *, Register>::iterator VRI =813 VRBaseMap.find(Pred.getSUnit());814 assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");815 // Find the destination physical register.816 Register Reg;817 for (const SDep &Succ : SU->Succs) {818 if (Succ.isCtrl())819 continue; // ignore chain preds820 if (Succ.getReg()) {821 Reg = Succ.getReg();822 break;823 }824 }825 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)826 .addReg(VRI->second);827 } else {828 // Copy from physical register.829 assert(Pred.getReg() && "Unknown physical register!");830 Register VRBase = MRI.createVirtualRegister(SU->CopyDstRC);831 bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;832 (void)isNew; // Silence compiler warning.833 assert(isNew && "Node emitted out of order - early");834 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)835 .addReg(Pred.getReg());836 }837 break;838 }839}840 841/// EmitSchedule - Emit the machine code in scheduled order. Return the new842/// InsertPos and MachineBasicBlock that contains this insertion843/// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does844/// not necessarily refer to returned BB. The emitter may split blocks.845MachineBasicBlock *ScheduleDAGSDNodes::846EmitSchedule(MachineBasicBlock::iterator &InsertPos) {847 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);848 InstrEmitter::VRBaseMapType VRBaseMap;849 SmallDenseMap<SUnit *, Register, 16> CopyVRBaseMap;850 SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;851 SmallSet<Register, 8> Seen;852 bool HasDbg = DAG->hasDebugValues();853 854 // Emit a node, and determine where its first instruction is for debuginfo.855 // Zero, one, or multiple instructions can be created when emitting a node.856 auto EmitNode =857 [&](SDNode *Node, bool IsClone, bool IsCloned,858 InstrEmitter::VRBaseMapType &VRBaseMap) -> MachineInstr * {859 // Fetch instruction prior to this, or end() if nonexistant.860 auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {861 if (I == BB->begin())862 return BB->end();863 else864 return std::prev(Emitter.getInsertPos());865 };866 867 MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());868 Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);869 MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());870 871 // If the iterator did not change, no instructions were inserted.872 if (Before == After)873 return nullptr;874 875 MachineInstr *MI;876 if (Before == BB->end()) {877 // There were no prior instructions; the new ones must start at the878 // beginning of the block.879 MI = &Emitter.getBlock()->instr_front();880 } else {881 // Return first instruction after the pre-existing instructions.882 MI = &*std::next(Before);883 }884 885 if (MI->isCandidateForAdditionalCallInfo()) {886 if (DAG->getTarget().Options.EmitCallSiteInfo ||887 DAG->getTarget().Options.EmitCallGraphSection)888 MF.addCallSiteInfo(MI, DAG->getCallSiteInfo(Node));889 890 if (auto CalledGlobal = DAG->getCalledGlobal(Node))891 if (CalledGlobal->Callee)892 MF.addCalledGlobal(MI, *CalledGlobal);893 }894 895 if (DAG->getNoMergeSiteInfo(Node)) {896 MI->setFlag(MachineInstr::MIFlag::NoMerge);897 }898 899 if (MDNode *MD = DAG->getPCSections(Node))900 MI->setPCSections(MF, MD);901 902 // Set MMRAs on _all_ added instructions.903 if (MDNode *MMRA = DAG->getMMRAMetadata(Node)) {904 for (MachineBasicBlock::iterator It = MI->getIterator(),905 End = std::next(After);906 It != End; ++It)907 It->setMMRAMetadata(MF, MMRA);908 }909 910 return MI;911 };912 913 // If this is the first BB, emit byval parameter dbg_value's.914 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {915 SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();916 SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();917 for (; PDI != PDE; ++PDI) {918 MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);919 if (DbgMI) {920 BB->insert(InsertPos, DbgMI);921 // We re-emit the dbg_value closer to its use, too, after instructions922 // are emitted to the BB.923 (*PDI)->clearIsEmitted();924 }925 }926 }927 928 for (SUnit *SU : Sequence) {929 if (!SU) {930 // Null SUnit* is a noop.931 TII->insertNoop(*Emitter.getBlock(), InsertPos);932 continue;933 }934 935 // For pre-regalloc scheduling, create instructions corresponding to the936 // SDNode and any glued SDNodes and append them to the block.937 if (!SU->getNode()) {938 // Emit a copy.939 EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);940 continue;941 }942 943 SmallVector<SDNode *, 4> GluedNodes;944 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())945 GluedNodes.push_back(N);946 while (!GluedNodes.empty()) {947 SDNode *N = GluedNodes.back();948 auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);949 // Remember the source order of the inserted instruction.950 if (HasDbg)951 ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);952 953 if (MDNode *MD = DAG->getHeapAllocSite(N))954 if (NewInsn && NewInsn->isCall())955 NewInsn->setHeapAllocMarker(MF, MD);956 957 GluedNodes.pop_back();958 }959 auto NewInsn =960 EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);961 // Remember the source order of the inserted instruction.962 if (HasDbg)963 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,964 NewInsn);965 966 if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {967 if (NewInsn && NewInsn->isCall())968 NewInsn->setHeapAllocMarker(MF, MD);969 }970 }971 972 // Insert all the dbg_values which have not already been inserted in source973 // order sequence.974 if (HasDbg) {975 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();976 977 // Sort the source order instructions and use the order to insert debug978 // values. Use stable_sort so that DBG_VALUEs are inserted in the same order979 // regardless of the host's implementation fo std::sort.980 llvm::stable_sort(Orders, less_first());981 std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),982 [](const SDDbgValue *LHS, const SDDbgValue *RHS) {983 return LHS->getOrder() < RHS->getOrder();984 });985 986 SDDbgInfo::DbgIterator DI = DAG->DbgBegin();987 SDDbgInfo::DbgIterator DE = DAG->DbgEnd();988 // Now emit the rest according to source order.989 unsigned LastOrder = 0;990 for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {991 unsigned Order = Orders[i].first;992 MachineInstr *MI = Orders[i].second;993 // Insert all SDDbgValue's whose order(s) are before "Order".994 assert(MI);995 for (; DI != DE; ++DI) {996 if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)997 break;998 if ((*DI)->isEmitted())999 continue;1000 1001 MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);1002 if (DbgMI) {1003 if (!LastOrder)1004 // Insert to start of the BB (after PHIs).1005 BB->insert(BBBegin, DbgMI);1006 else {1007 // Insert at the instruction, which may be in a different1008 // block, if the block was split by a custom inserter.1009 MachineBasicBlock::iterator Pos = MI;1010 MI->getParent()->insert(Pos, DbgMI);1011 }1012 }1013 }1014 LastOrder = Order;1015 }1016 // Add trailing DbgValue's before the terminator. FIXME: May want to add1017 // some of them before one or more conditional branches?1018 SmallVector<MachineInstr*, 8> DbgMIs;1019 for (; DI != DE; ++DI) {1020 if ((*DI)->isEmitted())1021 continue;1022 assert((*DI)->getOrder() >= LastOrder &&1023 "emitting DBG_VALUE out of order");1024 if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))1025 DbgMIs.push_back(DbgMI);1026 }1027 1028 MachineBasicBlock *InsertBB = Emitter.getBlock();1029 MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator();1030 InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());1031 1032 SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();1033 SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();1034 // Now emit the rest according to source order.1035 LastOrder = 0;1036 for (const auto &InstrOrder : Orders) {1037 unsigned Order = InstrOrder.first;1038 MachineInstr *MI = InstrOrder.second;1039 if (!MI)1040 continue;1041 1042 // Insert all SDDbgLabel's whose order(s) are before "Order".1043 for (; DLI != DLE &&1044 (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;1045 ++DLI) {1046 MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);1047 if (DbgMI) {1048 if (!LastOrder)1049 // Insert to start of the BB (after PHIs).1050 BB->insert(BBBegin, DbgMI);1051 else {1052 // Insert at the instruction, which may be in a different1053 // block, if the block was split by a custom inserter.1054 MachineBasicBlock::iterator Pos = MI;1055 MI->getParent()->insert(Pos, DbgMI);1056 }1057 }1058 }1059 if (DLI == DLE)1060 break;1061 1062 LastOrder = Order;1063 }1064 }1065 1066 InsertPos = Emitter.getInsertPos();1067 // In some cases, DBG_VALUEs might be inserted after the first terminator,1068 // which results in an invalid MBB. If that happens, move the DBG_VALUEs1069 // before the first terminator.1070 MachineBasicBlock *InsertBB = Emitter.getBlock();1071 auto FirstTerm = InsertBB->getFirstTerminator();1072 if (FirstTerm != InsertBB->end()) {1073 assert(!FirstTerm->isDebugValue() &&1074 "first terminator cannot be a debug value");1075 for (MachineInstr &MI : make_early_inc_range(1076 make_range(std::next(FirstTerm), InsertBB->end()))) {1077 // Only scan up to insertion point.1078 if (&MI == InsertPos)1079 break;1080 1081 if (!MI.isDebugValue())1082 continue;1083 1084 // The DBG_VALUE was referencing a value produced by a terminator. By1085 // moving the DBG_VALUE, the referenced value also needs invalidating.1086 MI.getOperand(0).ChangeToRegister(0, false);1087 MI.moveBefore(&*FirstTerm);1088 }1089 }1090 return InsertBB;1091}1092 1093/// Return the basic block label.1094std::string ScheduleDAGSDNodes::getDAGName() const {1095 return "sunit-dag." + BB->getFullName();1096}1097