12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064 |
- #include "ScheduleDAGSDNodes.h"
- #include "InstrEmitter.h"
- #include "SDNodeDbgValue.h"
- #include "llvm/ADT/DenseMap.h"
- #include "llvm/ADT/SmallPtrSet.h"
- #include "llvm/ADT/SmallSet.h"
- #include "llvm/ADT/SmallVector.h"
- #include "llvm/ADT/Statistic.h"
- #include "llvm/CodeGen/MachineInstrBuilder.h"
- #include "llvm/CodeGen/MachineRegisterInfo.h"
- #include "llvm/CodeGen/SelectionDAG.h"
- #include "llvm/CodeGen/TargetInstrInfo.h"
- #include "llvm/CodeGen/TargetLowering.h"
- #include "llvm/CodeGen/TargetRegisterInfo.h"
- #include "llvm/CodeGen/TargetSubtargetInfo.h"
- #include "llvm/Config/llvm-config.h"
- #include "llvm/MC/MCInstrItineraries.h"
- #include "llvm/Support/CommandLine.h"
- #include "llvm/Support/Debug.h"
- #include "llvm/Support/raw_ostream.h"
- #include "llvm/Target/TargetMachine.h"
- using namespace llvm;
- #define DEBUG_TYPE "pre-RA-sched"
- STATISTIC(LoadsClustered, "Number of loads clustered together");
- static cl::opt<int> HighLatencyCycles(
- "sched-high-latency-cycles", cl::Hidden, cl::init(10),
- cl::desc("Roughly estimate the number of cycles that 'long latency'"
- "instructions take for targets with no itinerary"));
- ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf)
- : ScheduleDAG(mf), BB(nullptr), DAG(nullptr),
- InstrItins(mf.getSubtarget().getInstrItineraryData()) {}
- void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) {
- BB = bb;
- DAG = dag;
-
- ScheduleDAG::clearDAG();
- Sequence.clear();
-
- Schedule();
- }
- SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) {
- #ifndef NDEBUG
- const SUnit *Addr = nullptr;
- if (!SUnits.empty())
- Addr = &SUnits[0];
- #endif
- SUnits.emplace_back(N, (unsigned)SUnits.size());
- assert((Addr == nullptr || Addr == &SUnits[0]) &&
- "SUnits std::vector reallocated on the fly!");
- SUnits.back().OrigNode = &SUnits.back();
- SUnit *SU = &SUnits.back();
- const TargetLowering &TLI = DAG->getTargetLoweringInfo();
- if (!N ||
- (N->isMachineOpcode() &&
- N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))
- SU->SchedulingPref = Sched::None;
- else
- SU->SchedulingPref = TLI.getSchedulingPreference(N);
- return SU;
- }
- SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
- SUnit *SU = newSUnit(Old->getNode());
- SU->OrigNode = Old->OrigNode;
- SU->Latency = Old->Latency;
- SU->isVRegCycle = Old->isVRegCycle;
- SU->isCall = Old->isCall;
- SU->isCallOp = Old->isCallOp;
- SU->isTwoAddress = Old->isTwoAddress;
- SU->isCommutable = Old->isCommutable;
- SU->hasPhysRegDefs = Old->hasPhysRegDefs;
- SU->hasPhysRegClobbers = Old->hasPhysRegClobbers;
- SU->isScheduleHigh = Old->isScheduleHigh;
- SU->isScheduleLow = Old->isScheduleLow;
- SU->SchedulingPref = Old->SchedulingPref;
- Old->isCloned = true;
- return SU;
- }
- static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
- const TargetRegisterInfo *TRI,
- const TargetInstrInfo *TII,
- unsigned &PhysReg, int &Cost) {
- if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
- return;
- unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
- if (Register::isVirtualRegister(Reg))
- return;
- unsigned ResNo = User->getOperand(2).getResNo();
- if (Def->getOpcode() == ISD::CopyFromReg &&
- cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
- PhysReg = Reg;
- } else if (Def->isMachineOpcode()) {
- const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
- if (ResNo >= II.getNumDefs() && II.hasImplicitDefOfPhysReg(Reg))
- PhysReg = Reg;
- }
- if (PhysReg != 0) {
- const TargetRegisterClass *RC =
- TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
- Cost = RC->getCopyCost();
- }
- }
- static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef<EVT> VTs,
- SDValue ExtraOper = SDValue()) {
- SmallVector<SDValue, 8> Ops(N->op_begin(), N->op_end());
- if (ExtraOper.getNode())
- Ops.push_back(ExtraOper);
- SDVTList VTList = DAG->getVTList(VTs);
- MachineSDNode *MN = dyn_cast<MachineSDNode>(N);
-
- SmallVector<MachineMemOperand *, 2> MMOs;
- if (MN)
- MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
- DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
-
- if (MN)
- DAG->setNodeMemRefs(MN, MMOs);
- }
- static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {
- SDNode *GlueDestNode = Glue.getNode();
-
- if (GlueDestNode == N) return false;
-
- if (GlueDestNode &&
- N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
- return false;
- }
-
- if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
- SmallVector<EVT, 4> VTs(N->values());
- if (AddGlue)
- VTs.push_back(MVT::Glue);
- CloneNodeWithValues(N, DAG, VTs, Glue);
- return true;
- }
- static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) {
- assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
- !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
- "expected an unused glue value");
- CloneNodeWithValues(N, DAG,
- makeArrayRef(N->value_begin(), N->getNumValues() - 1));
- }
- void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
- SDValue Chain;
- unsigned NumOps = Node->getNumOperands();
- if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
- Chain = Node->getOperand(NumOps-1);
- if (!Chain)
- return;
-
-
-
- auto hasTiedInput = [this](const SDNode *N) {
- const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
- for (unsigned I = 0; I != MCID.getNumOperands(); ++I) {
- if (MCID.getOperandConstraint(I, MCOI::TIED_TO) != -1)
- return true;
- }
- return false;
- };
-
-
- SmallPtrSet<SDNode*, 16> Visited;
- SmallVector<int64_t, 4> Offsets;
- DenseMap<long long, SDNode*> O2SMap;
- bool Cluster = false;
- SDNode *Base = Node;
- if (hasTiedInput(Base))
- return;
-
-
- unsigned UseCount = 0;
- for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
- I != E && UseCount < 100; ++I, ++UseCount) {
- if (I.getUse().getResNo() != Chain.getResNo())
- continue;
- SDNode *User = *I;
- if (User == Node || !Visited.insert(User).second)
- continue;
- int64_t Offset1, Offset2;
- if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
- Offset1 == Offset2 ||
- hasTiedInput(User)) {
-
-
- continue;
- }
- if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
- Offsets.push_back(Offset1);
- O2SMap.insert(std::make_pair(Offset2, User));
- Offsets.push_back(Offset2);
- if (Offset2 < Offset1)
- Base = User;
- Cluster = true;
-
- UseCount = 0;
- }
- if (!Cluster)
- return;
-
- llvm::sort(Offsets);
-
- SmallVector<SDNode*, 4> Loads;
- unsigned NumLoads = 0;
- int64_t BaseOff = Offsets[0];
- SDNode *BaseLoad = O2SMap[BaseOff];
- Loads.push_back(BaseLoad);
- for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
- int64_t Offset = Offsets[i];
- SDNode *Load = O2SMap[Offset];
- if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
- break;
- Loads.push_back(Load);
- ++NumLoads;
- }
- if (NumLoads == 0)
- return;
-
-
- SDNode *Lead = Loads[0];
- SDValue InGlue = SDValue(nullptr, 0);
- if (AddGlue(Lead, InGlue, true, DAG))
- InGlue = SDValue(Lead, Lead->getNumValues() - 1);
- for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
- bool OutGlue = I < E - 1;
- SDNode *Load = Loads[I];
-
-
- if (AddGlue(Load, InGlue, OutGlue, DAG)) {
- if (OutGlue)
- InGlue = SDValue(Load, Load->getNumValues() - 1);
- ++LoadsClustered;
- }
- else if (!OutGlue && InGlue.getNode())
- RemoveUnusedGlue(InGlue.getNode(), DAG);
- }
- }
- void ScheduleDAGSDNodes::ClusterNodes() {
- for (SDNode &NI : DAG->allnodes()) {
- SDNode *Node = &NI;
- if (!Node || !Node->isMachineOpcode())
- continue;
- unsigned Opc = Node->getMachineOpcode();
- const MCInstrDesc &MCID = TII->get(Opc);
- if (MCID.mayLoad())
-
- ClusterNeighboringLoads(Node);
- }
- }
- void ScheduleDAGSDNodes::BuildSchedUnits() {
-
-
-
- unsigned NumNodes = 0;
- for (SDNode &NI : DAG->allnodes()) {
- NI.setNodeId(-1);
- ++NumNodes;
- }
-
-
-
-
-
- SUnits.reserve(NumNodes * 2);
-
- SmallVector<SDNode*, 64> Worklist;
- SmallPtrSet<SDNode*, 32> Visited;
- Worklist.push_back(DAG->getRoot().getNode());
- Visited.insert(DAG->getRoot().getNode());
- SmallVector<SUnit*, 8> CallSUnits;
- while (!Worklist.empty()) {
- SDNode *NI = Worklist.pop_back_val();
-
- for (const SDValue &Op : NI->op_values())
- if (Visited.insert(Op.getNode()).second)
- Worklist.push_back(Op.getNode());
- if (isPassiveNode(NI))
- continue;
-
- if (NI->getNodeId() != -1) continue;
- SUnit *NodeSUnit = newSUnit(NI);
-
-
-
-
- SDNode *N = NI;
- while (N->getNumOperands() &&
- N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
- N = N->getOperand(N->getNumOperands()-1).getNode();
- assert(N->getNodeId() == -1 && "Node already inserted!");
- N->setNodeId(NodeSUnit->NodeNum);
- if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
- NodeSUnit->isCall = true;
- }
-
- N = NI;
- while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
- SDValue GlueVal(N, N->getNumValues()-1);
-
- bool HasGlueUse = false;
- for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
- UI != E; ++UI)
- if (GlueVal.isOperandOf(*UI)) {
- HasGlueUse = true;
- assert(N->getNodeId() == -1 && "Node already inserted!");
- N->setNodeId(NodeSUnit->NodeNum);
- N = *UI;
- if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
- NodeSUnit->isCall = true;
- break;
- }
- if (!HasGlueUse) break;
- }
- if (NodeSUnit->isCall)
- CallSUnits.push_back(NodeSUnit);
-
-
-
- if (NI->getOpcode() == ISD::TokenFactor)
- NodeSUnit->isScheduleLow = true;
-
-
-
- NodeSUnit->setNode(N);
- assert(N->getNodeId() == -1 && "Node already inserted!");
- N->setNodeId(NodeSUnit->NodeNum);
-
- InitNumRegDefsLeft(NodeSUnit);
-
- computeLatency(NodeSUnit);
- }
-
- while (!CallSUnits.empty()) {
- SUnit *SU = CallSUnits.pop_back_val();
- for (const SDNode *SUNode = SU->getNode(); SUNode;
- SUNode = SUNode->getGluedNode()) {
- if (SUNode->getOpcode() != ISD::CopyToReg)
- continue;
- SDNode *SrcN = SUNode->getOperand(2).getNode();
- if (isPassiveNode(SrcN)) continue;
- SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
- SrcSU->isCallOp = true;
- }
- }
- }
- void ScheduleDAGSDNodes::AddSchedEdges() {
- const TargetSubtargetInfo &ST = MF.getSubtarget();
-
- bool UnitLatencies = forceUnitLatencies();
-
- for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
- SUnit *SU = &SUnits[su];
- SDNode *MainNode = SU->getNode();
- if (MainNode->isMachineOpcode()) {
- unsigned Opc = MainNode->getMachineOpcode();
- const MCInstrDesc &MCID = TII->get(Opc);
- for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
- if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
- SU->isTwoAddress = true;
- break;
- }
- }
- if (MCID.isCommutable())
- SU->isCommutable = true;
- }
-
- for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
- if (N->isMachineOpcode() &&
- TII->get(N->getMachineOpcode()).getImplicitDefs()) {
- SU->hasPhysRegClobbers = true;
- unsigned NumUsed = InstrEmitter::CountResults(N);
- while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
- --NumUsed;
- if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
- SU->hasPhysRegDefs = true;
- }
- for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
- SDNode *OpN = N->getOperand(i).getNode();
- unsigned DefIdx = N->getOperand(i).getResNo();
- if (isPassiveNode(OpN)) continue;
- SUnit *OpSU = &SUnits[OpN->getNodeId()];
- assert(OpSU && "Node has no SUnit!");
- if (OpSU == SU) continue;
- EVT OpVT = N->getOperand(i).getValueType();
- assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
- bool isChain = OpVT == MVT::Other;
- unsigned PhysReg = 0;
- int Cost = 1;
-
- CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
- assert((PhysReg == 0 || !isChain) &&
- "Chain dependence via physreg data?");
-
-
-
-
-
- if (Cost >= 0 && !StressSched)
- PhysReg = 0;
-
- unsigned OpLatency = isChain ? 1 : OpSU->Latency;
-
- if(isChain && OpN->getOpcode() == ISD::TokenFactor)
- OpLatency = 0;
- SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
- : SDep(OpSU, SDep::Data, PhysReg);
- Dep.setLatency(OpLatency);
- if (!isChain && !UnitLatencies) {
- computeOperandLatency(OpN, N, i, Dep);
- ST.adjustSchedDependency(OpSU, DefIdx, SU, i, Dep);
- }
- if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
-
-
-
-
-
-
-
-
- --OpSU->NumRegDefsLeft;
- }
- }
- }
- }
- }
- void ScheduleDAGSDNodes::BuildSchedGraph(AAResults *AA) {
-
- ClusterNodes();
-
- BuildSchedUnits();
-
- AddSchedEdges();
- }
- void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
-
- if (!Node)
- return;
- if (!Node->isMachineOpcode()) {
- if (Node->getOpcode() == ISD::CopyFromReg)
- NodeNumDefs = 1;
- else
- NodeNumDefs = 0;
- return;
- }
- unsigned POpc = Node->getMachineOpcode();
- if (POpc == TargetOpcode::IMPLICIT_DEF) {
-
- NodeNumDefs = 0;
- return;
- }
- if (POpc == TargetOpcode::PATCHPOINT &&
- Node->getValueType(0) == MVT::Other) {
-
-
-
- NodeNumDefs = 0;
- return;
- }
- unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
-
-
- NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
- DefIdx = 0;
- }
- ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU,
- const ScheduleDAGSDNodes *SD)
- : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) {
- InitNodeNumDefs();
- Advance();
- }
- void ScheduleDAGSDNodes::RegDefIter::Advance() {
- for (;Node;) {
- for (;DefIdx < NodeNumDefs; ++DefIdx) {
- if (!Node->hasAnyUseOfValue(DefIdx))
- continue;
- ValueType = Node->getSimpleValueType(DefIdx);
- ++DefIdx;
- return;
- }
- Node = Node->getGluedNode();
- if (!Node) {
- return;
- }
- InitNodeNumDefs();
- }
- }
- void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) {
- assert(SU->NumRegDefsLeft == 0 && "expect a new node");
- for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
- assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
- ++SU->NumRegDefsLeft;
- }
- }
- void ScheduleDAGSDNodes::computeLatency(SUnit *SU) {
- SDNode *N = SU->getNode();
-
-
-
- if (N && N->getOpcode() == ISD::TokenFactor) {
- SU->Latency = 0;
- return;
- }
-
- if (forceUnitLatencies()) {
- SU->Latency = 1;
- return;
- }
- if (!InstrItins || InstrItins->isEmpty()) {
- if (N && N->isMachineOpcode() &&
- TII->isHighLatencyDef(N->getMachineOpcode()))
- SU->Latency = HighLatencyCycles;
- else
- SU->Latency = 1;
- return;
- }
-
-
- SU->Latency = 0;
- for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
- if (N->isMachineOpcode())
- SU->Latency += TII->getInstrLatency(InstrItins, N);
- }
- void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use,
- unsigned OpIdx, SDep& dep) const{
-
- if (forceUnitLatencies())
- return;
- if (dep.getKind() != SDep::Data)
- return;
- unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
- if (Use->isMachineOpcode())
-
- OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
- int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
- if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg &&
- !BB->succ_empty()) {
- unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
- if (Register::isVirtualRegister(Reg))
-
-
-
- Latency = (Latency > 1) ? Latency - 1 : 1;
- }
- if (Latency >= 0)
- dep.setLatency(Latency);
- }
- void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {
- #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
- dumpNodeName(SU);
- dbgs() << ": ";
- if (!SU.getNode()) {
- dbgs() << "PHYS REG COPY\n";
- return;
- }
- SU.getNode()->dump(DAG);
- dbgs() << "\n";
- SmallVector<SDNode *, 4> GluedNodes;
- for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
- GluedNodes.push_back(N);
- while (!GluedNodes.empty()) {
- dbgs() << " ";
- GluedNodes.back()->dump(DAG);
- dbgs() << "\n";
- GluedNodes.pop_back();
- }
- #endif
- }
- void ScheduleDAGSDNodes::dump() const {
- #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
- if (EntrySU.getNode() != nullptr)
- dumpNodeAll(EntrySU);
- for (const SUnit &SU : SUnits)
- dumpNodeAll(SU);
- if (ExitSU.getNode() != nullptr)
- dumpNodeAll(ExitSU);
- #endif
- }
- #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
- void ScheduleDAGSDNodes::dumpSchedule() const {
- for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
- if (SUnit *SU = Sequence[i])
- dumpNode(*SU);
- else
- dbgs() << "**** NOOP ****\n";
- }
- }
- #endif
- #ifndef NDEBUG
- void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) {
- unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
- unsigned Noops = 0;
- for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
- if (!Sequence[i])
- ++Noops;
- assert(Sequence.size() - Noops == ScheduledNodes &&
- "The number of nodes scheduled doesn't match the expected number!");
- }
- #endif
- static void
- ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
- SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
- DenseMap<SDValue, Register> &VRBaseMap, unsigned Order) {
- if (!N->getHasDebugValue())
- return;
-
-
- MachineBasicBlock *BB = Emitter.getBlock();
- MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
- for (auto DV : DAG->GetDbgValues(N)) {
- if (DV->isEmitted())
- continue;
- unsigned DVOrder = DV->getOrder();
- if (!Order || DVOrder == Order) {
- MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
- if (DbgMI) {
- Orders.push_back({DVOrder, DbgMI});
- BB->insert(InsertPos, DbgMI);
- }
- }
- }
- }
- static void
- ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
- DenseMap<SDValue, Register> &VRBaseMap,
- SmallVectorImpl<std::pair<unsigned, MachineInstr *>> &Orders,
- SmallSet<Register, 8> &Seen, MachineInstr *NewInsn) {
- unsigned Order = N->getIROrder();
- if (!Order || Seen.count(Order)) {
-
-
- ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
- return;
- }
-
-
-
-
- if (NewInsn) {
- Seen.insert(Order);
- Orders.push_back({Order, NewInsn});
- }
-
-
- ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
- }
- void ScheduleDAGSDNodes::
- EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, Register> &VRBaseMap,
- MachineBasicBlock::iterator InsertPos) {
- for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
- I != E; ++I) {
- if (I->isCtrl()) continue;
- if (I->getSUnit()->CopyDstRC) {
-
- DenseMap<SUnit*, Register>::iterator VRI = VRBaseMap.find(I->getSUnit());
- assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
-
- Register Reg;
- for (SUnit::const_succ_iterator II = SU->Succs.begin(),
- EE = SU->Succs.end(); II != EE; ++II) {
- if (II->isCtrl()) continue;
- if (II->getReg()) {
- Reg = II->getReg();
- break;
- }
- }
- BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
- .addReg(VRI->second);
- } else {
-
- assert(I->getReg() && "Unknown physical register!");
- Register VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
- bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
- (void)isNew;
- assert(isNew && "Node emitted out of order - early");
- BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
- .addReg(I->getReg());
- }
- break;
- }
- }
- MachineBasicBlock *ScheduleDAGSDNodes::
- EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
- InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos);
- DenseMap<SDValue, Register> VRBaseMap;
- DenseMap<SUnit*, Register> CopyVRBaseMap;
- SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;
- SmallSet<Register, 8> Seen;
- bool HasDbg = DAG->hasDebugValues();
-
-
- auto EmitNode =
- [&](SDNode *Node, bool IsClone, bool IsCloned,
- DenseMap<SDValue, Register> &VRBaseMap) -> MachineInstr * {
-
- auto GetPrevInsn = [&](MachineBasicBlock::iterator I) {
- if (I == BB->begin())
- return BB->end();
- else
- return std::prev(Emitter.getInsertPos());
- };
- MachineBasicBlock::iterator Before = GetPrevInsn(Emitter.getInsertPos());
- Emitter.EmitNode(Node, IsClone, IsCloned, VRBaseMap);
- MachineBasicBlock::iterator After = GetPrevInsn(Emitter.getInsertPos());
-
- if (Before == After)
- return nullptr;
- MachineInstr *MI;
- if (Before == BB->end()) {
-
-
- MI = &Emitter.getBlock()->instr_front();
- } else {
-
- MI = &*std::next(Before);
- }
- if (MI->isCandidateForCallSiteEntry() &&
- DAG->getTarget().Options.EmitCallSiteInfo)
- MF.addCallArgsForwardingRegs(MI, DAG->getSDCallSiteInfo(Node));
- if (DAG->getNoMergeSiteInfo(Node)) {
- MI->setFlag(MachineInstr::MIFlag::NoMerge);
- }
- return MI;
- };
-
- if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
- SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
- SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
- for (; PDI != PDE; ++PDI) {
- MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
- if (DbgMI) {
- BB->insert(InsertPos, DbgMI);
-
-
- (*PDI)->clearIsEmitted();
- }
- }
- }
- for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
- SUnit *SU = Sequence[i];
- if (!SU) {
-
- TII->insertNoop(*Emitter.getBlock(), InsertPos);
- continue;
- }
-
-
- if (!SU->getNode()) {
-
- EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
- continue;
- }
- SmallVector<SDNode *, 4> GluedNodes;
- for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
- GluedNodes.push_back(N);
- while (!GluedNodes.empty()) {
- SDNode *N = GluedNodes.back();
- auto NewInsn = EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
-
- if (HasDbg)
- ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen, NewInsn);
- if (MDNode *MD = DAG->getHeapAllocSite(N))
- if (NewInsn && NewInsn->isCall())
- NewInsn->setHeapAllocMarker(MF, MD);
- GluedNodes.pop_back();
- }
- auto NewInsn =
- EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned, VRBaseMap);
-
- if (HasDbg)
- ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders, Seen,
- NewInsn);
- if (MDNode *MD = DAG->getHeapAllocSite(SU->getNode())) {
- if (NewInsn && NewInsn->isCall())
- NewInsn->setHeapAllocMarker(MF, MD);
- }
- }
-
-
- if (HasDbg) {
- MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
-
-
-
- llvm::stable_sort(Orders, less_first());
- std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
- [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
- return LHS->getOrder() < RHS->getOrder();
- });
- SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
- SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
-
- unsigned LastOrder = 0;
- for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
- unsigned Order = Orders[i].first;
- MachineInstr *MI = Orders[i].second;
-
- assert(MI);
- for (; DI != DE; ++DI) {
- if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
- break;
- if ((*DI)->isEmitted())
- continue;
- MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
- if (DbgMI) {
- if (!LastOrder)
-
- BB->insert(BBBegin, DbgMI);
- else {
-
-
- MachineBasicBlock::iterator Pos = MI;
- MI->getParent()->insert(Pos, DbgMI);
- }
- }
- }
- LastOrder = Order;
- }
-
-
- SmallVector<MachineInstr*, 8> DbgMIs;
- for (; DI != DE; ++DI) {
- if ((*DI)->isEmitted())
- continue;
- assert((*DI)->getOrder() >= LastOrder &&
- "emitting DBG_VALUE out of order");
- if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
- DbgMIs.push_back(DbgMI);
- }
- MachineBasicBlock *InsertBB = Emitter.getBlock();
- MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator();
- InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
- SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();
- SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();
-
- LastOrder = 0;
- for (const auto &InstrOrder : Orders) {
- unsigned Order = InstrOrder.first;
- MachineInstr *MI = InstrOrder.second;
- if (!MI)
- continue;
-
- for (; DLI != DLE &&
- (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
- ++DLI) {
- MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
- if (DbgMI) {
- if (!LastOrder)
-
- BB->insert(BBBegin, DbgMI);
- else {
-
-
- MachineBasicBlock::iterator Pos = MI;
- MI->getParent()->insert(Pos, DbgMI);
- }
- }
- }
- if (DLI == DLE)
- break;
- LastOrder = Order;
- }
- }
- InsertPos = Emitter.getInsertPos();
-
-
-
- MachineBasicBlock *InsertBB = Emitter.getBlock();
- auto FirstTerm = InsertBB->getFirstTerminator();
- if (FirstTerm != InsertBB->end()) {
- assert(!FirstTerm->isDebugValue() &&
- "first terminator cannot be a debug value");
- for (MachineInstr &MI : make_early_inc_range(
- make_range(std::next(FirstTerm), InsertBB->end()))) {
- if (!MI.isDebugValue())
- continue;
- if (&MI == InsertPos)
- InsertPos = std::prev(InsertPos->getIterator());
-
-
- MI.getOperand(0).ChangeToRegister(0, false);
- MI.moveBefore(&*FirstTerm);
- }
- }
- return InsertBB;
- }
- std::string ScheduleDAGSDNodes::getDAGName() const {
- return "sunit-dag." + BB->getFullName();
- }
|