Lines Matching +full:fetch +full:- +full:depth
1 //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
29 #include "llvm/Config/llvm-config.h"
38 #define DEBUG_TYPE "pre-RA-sched"
42 // This allows the latency-based scheduler to notice high latency instructions
46 "sched-high-latency-cycles", cl::Hidden, cl::init(10),
53 /// Run - perform scheduling.
67 /// NewSUnit - Creates a new SUnit and return a ptr to it.
80 const TargetLowering &TLI = DAG->getTargetLoweringInfo();
82 (N->isMachineOpcode() &&
83 N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))
84 SU->SchedulingPref = Sched::None;
86 SU->SchedulingPref = TLI.getSchedulingPreference(N);
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;
108 /// CheckForPhysRegDependency - Check if the dependency between def and use of
116 if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
119 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
126 unsigned ResNo = User->getOperand(2).getResNo();
127 if (Def->getOpcode() == ISD::CopyFromReg &&
128 cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
130 } else if (Def->isMachineOpcode()) {
131 const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
138 TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
139 Cost = RC->getCopyCost();
146 SmallVector<SDValue, 8> Ops(N->ops());
150 SDVTList VTList = DAG->getVTList(VTs);
156 MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
158 DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
162 DAG->setNodeMemRefs(MN, MMOs);
173 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
177 if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
179 SmallVector<EVT, 4> VTs(N->values());
191 assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
192 !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
196 ArrayRef(N->value_begin(), N->getNumValues() - 1));
199 /// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
206 unsigned NumOps = Node->getNumOperands();
207 if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
208 Chain = Node->getOperand(NumOps-1);
216 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
218 if (MCID.getOperandConstraint(I, MCOI::TIED_TO) != -1)
239 for (SDNode::user_iterator I = Chain->user_begin(), E = Chain->user_end();
248 if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
281 if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
295 InGlue = SDValue(Lead, Lead->getNumValues() - 1);
297 bool OutGlue = I < E - 1;
304 InGlue = SDValue(Load, Load->getNumValues() - 1);
313 /// ClusterNodes - Cluster certain nodes which should be scheduled together.
316 for (SDNode &NI : DAG->allnodes()) {
318 if (!Node || !Node->isMachineOpcode())
321 unsigned Opc = Node->getMachineOpcode();
322 const MCInstrDesc &MCID = TII->get(Opc);
332 // of -1 means the SDNode does not yet have an associated SUnit.
334 for (SDNode &NI : DAG->allnodes()) {
335 NI.setNodeId(-1);
346 // Add all nodes in depth first order.
349 Worklist.push_back(DAG->getRoot().getNode());
350 Visited.insert(DAG->getRoot().getNode());
357 for (const SDValue &Op : NI->op_values())
365 if (NI->getNodeId() != -1) continue;
375 while (N->getNumOperands() &&
376 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
377 N = N->getOperand(N->getNumOperands()-1).getNode();
378 assert(N->getNodeId() == -1 && "Node already inserted!");
379 N->setNodeId(NodeSUnit->NodeNum);
380 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
381 NodeSUnit->isCall = true;
386 while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
387 SDValue GlueVal(N, N->getNumValues()-1);
391 for (SDNode *U : N->users())
394 assert(N->getNodeId() == -1 && "Node already inserted!");
395 N->setNodeId(NodeSUnit->NodeNum);
397 if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
398 NodeSUnit->isCall = true;
404 if (NodeSUnit->isCall)
407 // Schedule zero-latency TokenFactor below any nodes that may increase the
410 if (NI->getOpcode() == ISD::TokenFactor)
411 NodeSUnit->isScheduleLow = true;
413 // If there are glue operands involved, N is now the bottom-most node
416 NodeSUnit->setNode(N);
417 assert(N->getNodeId() == -1 && "Node already inserted!");
418 N->setNodeId(NodeSUnit->NodeNum);
423 // Assign the Latency field of NodeSUnit using target-provided information.
430 for (const SDNode *SUNode = SU->getNode(); SUNode;
431 SUNode = SUNode->getGluedNode()) {
432 if (SUNode->getOpcode() != ISD::CopyToReg)
434 SDNode *SrcN = SUNode->getOperand(2).getNode();
436 SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
437 SrcSU->isCallOp = true;
452 if (MainNode->isMachineOpcode()) {
453 unsigned Opc = MainNode->getMachineOpcode();
454 const MCInstrDesc &MCID = TII->get(Opc);
456 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
466 for (SDNode *N = SU.getNode(); N; N = N->getGluedNode()) {
467 if (N->isMachineOpcode() &&
468 !TII->get(N->getMachineOpcode()).implicit_defs().empty()) {
471 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
472 --NumUsed; // Skip over unused values at the end.
473 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
477 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
478 SDNode *OpN = N->getOperand(i).getNode();
479 unsigned DefIdx = N->getOperand(i).getResNo();
481 SUnit *OpSU = &SUnits[OpN->getNodeId()];
486 EVT OpVT = N->getOperand(i).getValueType();
493 const TargetLowering &TLI = DAG->getTargetLoweringInfo();
506 unsigned OpLatency = isChain ? 1 : OpSU->Latency;
507 // Special-case TokenFactor chains as zero-latency.
508 if(isChain && OpN->getOpcode() == ISD::TokenFactor)
519 if (!SU.addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
525 // We can't tell (without more book-keeping) if this results from
528 --OpSU->NumRegDefsLeft;
535 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
554 if (!Node->isMachineOpcode()) {
555 if (Node->getOpcode() == ISD::CopyFromReg)
561 unsigned POpc = Node->getMachineOpcode();
568 Node->getValueType(0) == MVT::Other) {
575 unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
578 NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
585 : SchedDAG(SD), Node(SU->getNode()) {
594 if (!Node->hasAnyUseOfValue(DefIdx))
596 ValueType = Node->getSimpleValueType(DefIdx);
600 Node = Node->getGluedNode();
609 assert(SU->NumRegDefsLeft == 0 && "expect a new node");
611 assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
612 ++SU->NumRegDefsLeft;
617 SDNode *N = SU->getNode();
620 // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
622 if (N && N->getOpcode() == ISD::TokenFactor) {
623 SU->Latency = 0;
629 SU->Latency = 1;
633 if (!InstrItins || InstrItins->isEmpty()) {
634 if (N && N->isMachineOpcode() &&
635 TII->isHighLatencyDef(N->getMachineOpcode()))
636 SU->Latency = HighLatencyCycles;
638 SU->Latency = 1;
644 SU->Latency = 0;
645 for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
646 if (N->isMachineOpcode())
647 SU->Latency += TII->getInstrLatency(InstrItins, N);
659 unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
660 if (Use->isMachineOpcode())
662 OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
664 TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
665 if (Latency > 1U && Use->getOpcode() == ISD::CopyToReg &&
666 !BB->succ_empty()) {
667 unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
672 Latency = *Latency - 1;
688 SU.getNode()->dump(DAG);
691 for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
695 GluedNodes.back()->dump(DAG);
725 /// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
731 assert(Sequence.size() - Noops == ScheduledNodes &&
736 /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
741 if (!N->getHasDebugValue())
747 for (const SDDbgOperand &L : DV->getLocationOps()) {
759 for (auto *DV : DAG->GetDbgValues(N)) {
760 if (DV->isEmitted())
762 unsigned DVOrder = DV->getOrder();
770 if (!DV->isInvalidated() && HasUnknownVReg(DV))
776 BB->insert(InsertPos, DbgMI);
780 // ProcessSourceNode - Process nodes with source order numbers. These are added
788 unsigned Order = N->getIROrder();
813 for (const SDep &Pred : SU->Preds) {
816 if (Pred.getSUnit()->CopyDstRC) {
820 assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
823 for (const SDep &Succ : SU->Succs) {
831 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
832 .addReg(VRI->second);
836 Register VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
839 assert(isNew && "Node emitted out of order - early");
840 BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
847 /// EmitSchedule - Emit the machine code in scheduled order. Return the new
853 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
858 bool HasDbg = DAG->hasDebugValues();
864 InstrEmitter::VRBaseMapType &VRBaseMap) -> MachineInstr * {
865 // Fetch instruction prior to this, or end() if nonexistant.
867 if (I == BB->begin())
868 return BB->end();
882 if (Before == BB->end()) {
885 MI = &Emitter.getBlock()->instr_front();
887 // Return first instruction after the pre-existing instructions.
891 if (MI->isCandidateForAdditionalCallInfo()) {
892 if (DAG->getTarget().Options.EmitCallSiteInfo)
893 MF.addCallSiteInfo(MI, DAG->getCallSiteInfo(Node));
895 if (auto CalledGlobal = DAG->getCalledGlobal(Node))
896 if (CalledGlobal->Callee)
900 if (DAG->getNoMergeSiteInfo(Node)) {
901 MI->setFlag(MachineInstr::MIFlag::NoMerge);
904 if (MDNode *MD = DAG->getPCSections(Node))
905 MI->setPCSections(MF, MD);
908 if (MDNode *MMRA = DAG->getMMRAMetadata(Node)) {
909 for (MachineBasicBlock::iterator It = MI->getIterator(),
912 It->setMMRAMetadata(MF, MMRA);
919 if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
920 SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
921 SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
925 BB->insert(InsertPos, DbgMI);
926 // We re-emit the dbg_value closer to its use, too, after instructions
928 (*PDI)->clearIsEmitted();
936 TII->insertNoop(*Emitter.getBlock(), InsertPos);
940 // For pre-regalloc scheduling, create instructions corresponding to the
942 if (!SU->getNode()) {
949 for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
953 auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
958 if (MDNode *MD = DAG->getHeapAllocSite(N))
959 if (NewInsn && NewInsn->isCall())
960 NewInsn->setHeapAllocMarker(MF, MD);
965 EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
968 ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
971 if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
972 if (NewInsn && NewInsn->isCall())
973 NewInsn->setHeapAllocMarker(MF, MD);
980 MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
986 std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
988 return LHS->getOrder() < RHS->getOrder();
991 SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
992 SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
1001 if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
1003 if ((*DI)->isEmitted())
1010 BB->insert(BBBegin, DbgMI);
1015 MI->getParent()->insert(Pos, DbgMI);
1025 if ((*DI)->isEmitted())
1027 assert((*DI)->getOrder() >= LastOrder &&
1034 MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator();
1035 InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
1037 SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();
1038 SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();
1049 (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
1055 BB->insert(BBBegin, DbgMI);
1060 MI->getParent()->insert(Pos, DbgMI);
1076 auto FirstTerm = InsertBB->getFirstTerminator();
1077 if (FirstTerm != InsertBB->end()) {
1078 assert(!FirstTerm->isDebugValue() &&
1081 make_range(std::next(FirstTerm), InsertBB->end()))) {
1100 return "sunit-dag." + BB->getFullName();