From c6be777208f4539af400ac694d9d1dc8b992bc80 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Wed, 2 Jul 2008 09:23:51 +0000 Subject: [PATCH] - Use a faster priority comparison function if -fast. - Code clean up. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53010 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SelectionDAG/ScheduleDAG.cpp | 273 +++++++++--------- .../SelectionDAG/ScheduleDAGRRList.cpp | 259 +++++++++++------ 2 files changed, 304 insertions(+), 228 deletions(-) diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index de2c1bc90aa..b5889fc677a 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -224,26 +224,26 @@ void ScheduleDAG::ComputeLatency(SUnit *SU) { if (InstrItins.isEmpty()) { // No latency information. SU->Latency = 1; - } else { - SU->Latency = 0; - if (SU->Node->isTargetOpcode()) { - unsigned SchedClass = - TII->get(SU->Node->getTargetOpcode()).getSchedClass(); + return; + } + + SU->Latency = 0; + if (SU->Node->isTargetOpcode()) { + unsigned SchedClass = TII->get(SU->Node->getTargetOpcode()).getSchedClass(); + const InstrStage *S = InstrItins.begin(SchedClass); + const InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + SU->Latency += S->Cycles; + } + for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) { + SDNode *FNode = SU->FlaggedNodes[i]; + if (FNode->isTargetOpcode()) { + unsigned SchedClass = TII->get(FNode->getTargetOpcode()).getSchedClass(); const InstrStage *S = InstrItins.begin(SchedClass); const InstrStage *E = InstrItins.end(SchedClass); for (; S != E; ++S) SU->Latency += S->Cycles; } - for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) { - SDNode *FNode = SU->FlaggedNodes[i]; - if (FNode->isTargetOpcode()) { - unsigned SchedClass =TII->get(FNode->getTargetOpcode()).getSchedClass(); - const InstrStage *S = InstrItins.begin(SchedClass); - const InstrStage *E = InstrItins.end(SchedClass); - for (; S != E; ++S) - SU->Latency += S->Cycles; - } - } } } @@ -390,11 +390,12 @@ unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) { return N; } -static const TargetRegisterClass *getInstrOperandRegClass( - const TargetRegisterInfo *TRI, - const TargetInstrInfo *TII, - const TargetInstrDesc &II, - unsigned Op) { +/// getInstrOperandRegClass - Return register class of the operand of an +/// instruction of the specified TargetInstrDesc. +static const TargetRegisterClass* +getInstrOperandRegClass(const TargetRegisterInfo *TRI, + const TargetInstrInfo *TII, const TargetInstrDesc &II, + unsigned Op) { if (Op >= II.getNumOperands()) { assert(II.isVariadic() && "Invalid operand # of instruction"); return NULL; @@ -404,6 +405,8 @@ static const TargetRegisterClass *getInstrOperandRegClass( return TRI->getRegClass(II.OpInfo[Op].RegClass); } +/// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an +/// implicit physical register output. void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, unsigned SrcReg, DenseMap &VRBaseMap) { @@ -660,18 +663,17 @@ void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op, assert(getInstrOperandRegClass(TRI, TII, *II, IIOpNum) && "Don't have operand info for this instruction!"); } - } - + } } void ScheduleDAG::AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO) { MI->addMemOperand(MO); } -// Returns the Register Class of a subregister -static const TargetRegisterClass *getSubRegisterRegClass( - const TargetRegisterClass *TRC, - unsigned SubIdx) { +/// getSubRegisterRegClass - Returns the register class of specified register +/// class' "SubIdx"'th sub-register class. +static const TargetRegisterClass* +getSubRegisterRegClass(const TargetRegisterClass *TRC, unsigned SubIdx) { // Pick the register class of the subregister TargetRegisterInfo::regclass_iterator I = TRC->subregclasses_begin() + SubIdx-1; @@ -680,10 +682,12 @@ static const TargetRegisterClass *getSubRegisterRegClass( return *I; } -static const TargetRegisterClass *getSuperregRegisterClass( - const TargetRegisterClass *TRC, - unsigned SubIdx, - MVT VT) { +/// getSuperRegisterRegClass - Returns the register class of a superreg A whose +/// "SubIdx"'th sub-register class is the specified register class and whose +/// type matches the specified type. +static const TargetRegisterClass* +getSuperRegisterRegClass(const TargetRegisterClass *TRC, + unsigned SubIdx, MVT VT) { // Pick the register class of the superegister for this type for (TargetRegisterInfo::regclass_iterator I = TRC->superregclasses_begin(), E = TRC->superregclasses_end(); I != E; ++I) @@ -758,7 +762,7 @@ void ScheduleDAG::EmitSubregNode(SDNode *Node, if (VRBase) { TRC = MRI.getRegClass(VRBase); } else { - TRC = getSuperregRegisterClass(MRI.getRegClass(SubReg), SubIdx, + TRC = getSuperRegisterRegClass(MRI.getRegClass(SubReg), SubIdx, Node->getValueType(0)); assert(TRC && "Couldn't determine register class for insert_subreg"); VRBase = MRI.createVirtualRegister(TRC); // Create the reg @@ -867,124 +871,125 @@ void ScheduleDAG::EmitNode(SDNode *Node, bool IsClone, EmitCopyFromReg(Node, i, IsClone, Reg, VRBaseMap); } } - } else { - switch (Node->getOpcode()) { - default: + return; + } + + switch (Node->getOpcode()) { + default: #ifndef NDEBUG - Node->dump(&DAG); + Node->dump(&DAG); #endif - assert(0 && "This target-independent node should have been selected!"); - break; - case ISD::EntryToken: - assert(0 && "EntryToken should have been excluded from the schedule!"); - break; - case ISD::TokenFactor: // fall thru - case ISD::DECLARE: - case ISD::SRCVALUE: - break; - case ISD::DBG_LABEL: - BB->push_back(BuildMI(TII->get(TargetInstrInfo::DBG_LABEL)) - .addImm(cast(Node)->getLabelID())); - break; - case ISD::EH_LABEL: - BB->push_back(BuildMI(TII->get(TargetInstrInfo::EH_LABEL)) - .addImm(cast(Node)->getLabelID())); - break; - case ISD::CopyToReg: { - unsigned SrcReg; - SDOperand SrcVal = Node->getOperand(2); - if (RegisterSDNode *R = dyn_cast(SrcVal)) - SrcReg = R->getReg(); - else - SrcReg = getVR(SrcVal, VRBaseMap); + assert(0 && "This target-independent node should have been selected!"); + break; + case ISD::EntryToken: + assert(0 && "EntryToken should have been excluded from the schedule!"); + break; + case ISD::TokenFactor: // fall thru + case ISD::DECLARE: + case ISD::SRCVALUE: + break; + case ISD::DBG_LABEL: + BB->push_back(BuildMI(TII->get(TargetInstrInfo::DBG_LABEL)) + .addImm(cast(Node)->getLabelID())); + break; + case ISD::EH_LABEL: + BB->push_back(BuildMI(TII->get(TargetInstrInfo::EH_LABEL)) + .addImm(cast(Node)->getLabelID())); + break; + case ISD::CopyToReg: { + unsigned SrcReg; + SDOperand SrcVal = Node->getOperand(2); + if (RegisterSDNode *R = dyn_cast(SrcVal)) + SrcReg = R->getReg(); + else + SrcReg = getVR(SrcVal, VRBaseMap); - unsigned DestReg = cast(Node->getOperand(1))->getReg(); - if (SrcReg == DestReg) // Coalesced away the copy? Ignore. - break; + unsigned DestReg = cast(Node->getOperand(1))->getReg(); + if (SrcReg == DestReg) // Coalesced away the copy? Ignore. + break; - const TargetRegisterClass *SrcTRC = 0, *DstTRC = 0; - // Get the register classes of the src/dst. - if (TargetRegisterInfo::isVirtualRegister(SrcReg)) - SrcTRC = MRI.getRegClass(SrcReg); - else - SrcTRC = TRI->getPhysicalRegisterRegClass(SrcReg,SrcVal.getValueType()); + const TargetRegisterClass *SrcTRC = 0, *DstTRC = 0; + // Get the register classes of the src/dst. + if (TargetRegisterInfo::isVirtualRegister(SrcReg)) + SrcTRC = MRI.getRegClass(SrcReg); + else + SrcTRC = TRI->getPhysicalRegisterRegClass(SrcReg,SrcVal.getValueType()); - if (TargetRegisterInfo::isVirtualRegister(DestReg)) - DstTRC = MRI.getRegClass(DestReg); - else - DstTRC = TRI->getPhysicalRegisterRegClass(DestReg, + if (TargetRegisterInfo::isVirtualRegister(DestReg)) + DstTRC = MRI.getRegClass(DestReg); + else + DstTRC = TRI->getPhysicalRegisterRegClass(DestReg, Node->getOperand(1).getValueType()); - TII->copyRegToReg(*BB, BB->end(), DestReg, SrcReg, DstTRC, SrcTRC); - break; - } - case ISD::CopyFromReg: { - unsigned SrcReg = cast(Node->getOperand(1))->getReg(); - EmitCopyFromReg(Node, 0, IsClone, SrcReg, VRBaseMap); - break; - } - case ISD::INLINEASM: { - unsigned NumOps = Node->getNumOperands(); - if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag) - --NumOps; // Ignore the flag operand. + TII->copyRegToReg(*BB, BB->end(), DestReg, SrcReg, DstTRC, SrcTRC); + break; + } + case ISD::CopyFromReg: { + unsigned SrcReg = cast(Node->getOperand(1))->getReg(); + EmitCopyFromReg(Node, 0, IsClone, SrcReg, VRBaseMap); + break; + } + case ISD::INLINEASM: { + unsigned NumOps = Node->getNumOperands(); + if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag) + --NumOps; // Ignore the flag operand. - // Create the inline asm machine instruction. - MachineInstr *MI = BuildMI(TII->get(TargetInstrInfo::INLINEASM)); + // Create the inline asm machine instruction. + MachineInstr *MI = BuildMI(TII->get(TargetInstrInfo::INLINEASM)); - // Add the asm string as an external symbol operand. - const char *AsmStr = - cast(Node->getOperand(1))->getSymbol(); - MI->addOperand(MachineOperand::CreateES(AsmStr)); + // Add the asm string as an external symbol operand. + const char *AsmStr = + cast(Node->getOperand(1))->getSymbol(); + MI->addOperand(MachineOperand::CreateES(AsmStr)); - // Add all of the operand registers to the instruction. - for (unsigned i = 2; i != NumOps;) { - unsigned Flags = cast(Node->getOperand(i))->getValue(); - unsigned NumVals = Flags >> 3; + // Add all of the operand registers to the instruction. + for (unsigned i = 2; i != NumOps;) { + unsigned Flags = cast(Node->getOperand(i))->getValue(); + unsigned NumVals = Flags >> 3; - MI->addOperand(MachineOperand::CreateImm(Flags)); - ++i; // Skip the ID value. + MI->addOperand(MachineOperand::CreateImm(Flags)); + ++i; // Skip the ID value. - switch (Flags & 7) { - default: assert(0 && "Bad flags!"); - case 1: // Use of register. - for (; NumVals; --NumVals, ++i) { - unsigned Reg = cast(Node->getOperand(i))->getReg(); - MI->addOperand(MachineOperand::CreateReg(Reg, false)); - } - break; - case 2: // Def of register. - for (; NumVals; --NumVals, ++i) { - unsigned Reg = cast(Node->getOperand(i))->getReg(); - MI->addOperand(MachineOperand::CreateReg(Reg, true)); - } - break; - case 3: { // Immediate. - for (; NumVals; --NumVals, ++i) { - if (ConstantSDNode *CS = - dyn_cast(Node->getOperand(i))) { - MI->addOperand(MachineOperand::CreateImm(CS->getValue())); - } else if (GlobalAddressSDNode *GA = - dyn_cast(Node->getOperand(i))) { - MI->addOperand(MachineOperand::CreateGA(GA->getGlobal(), - GA->getOffset())); - } else { - BasicBlockSDNode *BB =cast(Node->getOperand(i)); - MI->addOperand(MachineOperand::CreateMBB(BB->getBasicBlock())); - } - } - break; + switch (Flags & 7) { + default: assert(0 && "Bad flags!"); + case 1: // Use of register. + for (; NumVals; --NumVals, ++i) { + unsigned Reg = cast(Node->getOperand(i))->getReg(); + MI->addOperand(MachineOperand::CreateReg(Reg, false)); } - case 4: // Addressing mode. - // The addressing mode has been selected, just add all of the - // operands to the machine instruction. - for (; NumVals; --NumVals, ++i) - AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap); - break; + break; + case 2: // Def of register. + for (; NumVals; --NumVals, ++i) { + unsigned Reg = cast(Node->getOperand(i))->getReg(); + MI->addOperand(MachineOperand::CreateReg(Reg, true)); + } + break; + case 3: { // Immediate. + for (; NumVals; --NumVals, ++i) { + if (ConstantSDNode *CS = + dyn_cast(Node->getOperand(i))) { + MI->addOperand(MachineOperand::CreateImm(CS->getValue())); + } else if (GlobalAddressSDNode *GA = + dyn_cast(Node->getOperand(i))) { + MI->addOperand(MachineOperand::CreateGA(GA->getGlobal(), + GA->getOffset())); + } else { + BasicBlockSDNode *BB =cast(Node->getOperand(i)); + MI->addOperand(MachineOperand::CreateMBB(BB->getBasicBlock())); + } } + break; + } + case 4: // Addressing mode. + // The addressing mode has been selected, just add all of the + // operands to the machine instruction. + for (; NumVals; --NumVals, ++i) + AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap); + break; } - BB->push_back(MI); - break; - } } + BB->push_back(MI); + break; + } } } diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index f881737f999..287e8c5b0e5 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -59,6 +59,8 @@ private: /// it is top-down. bool isBottomUp; + /// Fast - True if we are performing fast scheduling. + /// bool Fast; /// AvailableQueue - The priority queue to use for the available SUnits. @@ -1257,6 +1259,15 @@ namespace { bool operator()(const SUnit* left, const SUnit* right) const; }; + struct bu_ls_rr_fast_sort : public std::binary_function{ + RegReductionPriorityQueue *SPQ; + bu_ls_rr_fast_sort(RegReductionPriorityQueue *spq) + : SPQ(spq) {} + bu_ls_rr_fast_sort(const bu_ls_rr_fast_sort &RHS) : SPQ(RHS.SPQ) {} + + bool operator()(const SUnit* left, const SUnit* right) const; + }; + struct td_ls_rr_sort : public std::binary_function { RegReductionPriorityQueue *SPQ; td_ls_rr_sort(RegReductionPriorityQueue *spq) : SPQ(spq) {} @@ -1272,6 +1283,76 @@ static inline bool isCopyFromLiveIn(const SUnit *SU) { N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; } +/// CalcNodeBUSethiUllmanNumber - Compute Sethi Ullman number for bottom up +/// scheduling. Smaller number is the higher priority. +static unsigned +CalcNodeBUSethiUllmanNumber(const SUnit *SU, std::vector &SUNumbers) { + unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum]; + if (SethiUllmanNumber != 0) + return SethiUllmanNumber; + + unsigned Extra = 0; + for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) { + if (I->isCtrl) continue; // ignore chain preds + SUnit *PredSU = I->Dep; + unsigned PredSethiUllman = CalcNodeBUSethiUllmanNumber(PredSU, SUNumbers); + if (PredSethiUllman > SethiUllmanNumber) { + SethiUllmanNumber = PredSethiUllman; + Extra = 0; + } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) + ++Extra; + } + + SethiUllmanNumber += Extra; + + if (SethiUllmanNumber == 0) + SethiUllmanNumber = 1; + + return SethiUllmanNumber; +} + +/// CalcNodeTDSethiUllmanNumber - Compute Sethi Ullman number for top down +/// scheduling. Smaller number is the higher priority. +static unsigned +CalcNodeTDSethiUllmanNumber(const SUnit *SU, std::vector &SUNumbers) { + unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum]; + if (SethiUllmanNumber != 0) + return SethiUllmanNumber; + + unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; + if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) + SethiUllmanNumber = 0xffff; + else if (SU->NumSuccsLeft == 0) + // If SU does not have a use, i.e. it doesn't produce a value that would + // be consumed (e.g. store), then it terminates a chain of computation. + // Give it a small SethiUllman number so it will be scheduled right before + // its predecessors that it doesn't lengthen their live ranges. + SethiUllmanNumber = 0; + else if (SU->NumPredsLeft == 0 && + (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) + SethiUllmanNumber = 0xffff; + else { + int Extra = 0; + for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) { + if (I->isCtrl) continue; // ignore chain preds + SUnit *PredSU = I->Dep; + unsigned PredSethiUllman = CalcNodeTDSethiUllmanNumber(PredSU, SUNumbers); + if (PredSethiUllman > SethiUllmanNumber) { + SethiUllmanNumber = PredSethiUllman; + Extra = 0; + } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) + ++Extra; + } + + SethiUllmanNumber += Extra; + } + + return SethiUllmanNumber; +} + + namespace { template class VISIBILITY_HIDDEN RegReductionPriorityQueue @@ -1338,30 +1419,29 @@ namespace { const TargetRegisterInfo *TRI; ScheduleDAGRRList *scheduleDAG; - bool Fast; public: explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii, - const TargetRegisterInfo *tri, - bool f) - : TII(tii), TRI(tri), scheduleDAG(NULL), Fast(f) {} + const TargetRegisterInfo *tri) + : TII(tii), TRI(tri), scheduleDAG(NULL) {} void initNodes(std::vector &sunits) { SUnits = &sunits; // Add pseudo dependency edges for two-address nodes. - if (!Fast) - AddPseudoTwoAddrDeps(); + AddPseudoTwoAddrDeps(); // Calculate node priorities. CalculateSethiUllmanNumbers(); } void addNode(const SUnit *SU) { - SethiUllmanNumbers.resize(SUnits->size(), 0); - CalcNodeSethiUllmanNumber(SU); + unsigned SUSize = SethiUllmanNumbers.size(); + if (SUnits->size() > SUSize) + SethiUllmanNumbers.resize(SUSize*2, 0); + CalcNodeBUSethiUllmanNumber(SU, SethiUllmanNumbers); } void updateNode(const SUnit *SU) { SethiUllmanNumbers[SU->NodeNum] = 0; - CalcNodeSethiUllmanNumber(SU); + CalcNodeBUSethiUllmanNumber(SU, SethiUllmanNumbers); } void releaseState() { @@ -1408,7 +1488,48 @@ namespace { bool canClobber(const SUnit *SU, const SUnit *Op); void AddPseudoTwoAddrDeps(); void CalculateSethiUllmanNumbers(); - unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); + }; + + + class VISIBILITY_HIDDEN BURegReductionFastPriorityQueue + : public RegReductionPriorityQueue { + // SUnits - The SUnits for the current graph. + const std::vector *SUnits; + + // SethiUllmanNumbers - The SethiUllman number for each node. + std::vector SethiUllmanNumbers; + public: + explicit BURegReductionFastPriorityQueue() {} + + void initNodes(std::vector &sunits) { + SUnits = &sunits; + // Calculate node priorities. + CalculateSethiUllmanNumbers(); + } + + void addNode(const SUnit *SU) { + unsigned SUSize = SethiUllmanNumbers.size(); + if (SUnits->size() > SUSize) + SethiUllmanNumbers.resize(SUSize*2, 0); + CalcNodeBUSethiUllmanNumber(SU, SethiUllmanNumbers); + } + + void updateNode(const SUnit *SU) { + SethiUllmanNumbers[SU->NodeNum] = 0; + CalcNodeBUSethiUllmanNumber(SU, SethiUllmanNumbers); + } + + void releaseState() { + SUnits = 0; + SethiUllmanNumbers.clear(); + } + + unsigned getNodePriority(const SUnit *SU) const { + return SethiUllmanNumbers[SU->NodeNum]; + } + + private: + void CalculateSethiUllmanNumbers(); }; @@ -1430,13 +1551,15 @@ namespace { } void addNode(const SUnit *SU) { - SethiUllmanNumbers.resize(SUnits->size(), 0); - CalcNodeSethiUllmanNumber(SU); + unsigned SUSize = SethiUllmanNumbers.size(); + if (SUnits->size() > SUSize) + SethiUllmanNumbers.resize(SUSize*2, 0); + CalcNodeTDSethiUllmanNumber(SU, SethiUllmanNumbers); } void updateNode(const SUnit *SU) { SethiUllmanNumbers[SU->NodeNum] = 0; - CalcNodeSethiUllmanNumber(SU); + CalcNodeTDSethiUllmanNumber(SU, SethiUllmanNumbers); } void releaseState() { @@ -1451,7 +1574,6 @@ namespace { private: void CalculateSethiUllmanNumbers(); - unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); }; } @@ -1494,7 +1616,6 @@ static unsigned calcMaxScratches(const SUnit *SU) { // Bottom up bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { - unsigned LPriority = SPQ->getNodePriority(left); unsigned RPriority = SPQ->getNodePriority(right); if (LPriority != RPriority) @@ -1545,6 +1666,17 @@ bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { return (left->NodeQueueId > right->NodeQueueId); } +bool +bu_ls_rr_fast_sort::operator()(const SUnit *left, const SUnit *right) const { + unsigned LPriority = SPQ->getNodePriority(left); + unsigned RPriority = SPQ->getNodePriority(right); + if (LPriority != RPriority) + return LPriority > RPriority; + assert(left->NodeQueueId && right->NodeQueueId && + "NodeQueueId cannot be zero"); + return (left->NodeQueueId > right->NodeQueueId); +} + bool BURegReductionPriorityQueue::canClobber(const SUnit *SU, const SUnit *Op) { if (SU->isTwoAddress) { @@ -1671,42 +1803,19 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() { } } -/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. -/// Smaller number is the higher priority. -unsigned BURegReductionPriorityQueue:: -CalcNodeSethiUllmanNumber(const SUnit *SU) { - unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; - if (SethiUllmanNumber != 0) - return SethiUllmanNumber; - - unsigned Extra = 0; - for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - if (I->isCtrl) continue; // ignore chain preds - SUnit *PredSU = I->Dep; - unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); - if (PredSethiUllman > SethiUllmanNumber) { - SethiUllmanNumber = PredSethiUllman; - Extra = 0; - } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) - ++Extra; - } - - SethiUllmanNumber += Extra; - - if (SethiUllmanNumber == 0) - SethiUllmanNumber = 1; - - return SethiUllmanNumber; -} - /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all /// scheduling units. void BURegReductionPriorityQueue::CalculateSethiUllmanNumbers() { SethiUllmanNumbers.assign(SUnits->size(), 0); for (unsigned i = 0, e = SUnits->size(); i != e; ++i) - CalcNodeSethiUllmanNumber(&(*SUnits)[i]); + CalcNodeBUSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers); +} +void BURegReductionFastPriorityQueue::CalculateSethiUllmanNumbers() { + SethiUllmanNumbers.assign(SUnits->size(), 0); + + for (unsigned i = 0, e = SUnits->size(); i != e; ++i) + CalcNodeBUSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers); } /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled @@ -1772,53 +1881,13 @@ bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { return (left->NodeQueueId > right->NodeQueueId); } -/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. -/// Smaller number is the higher priority. -unsigned TDRegReductionPriorityQueue:: -CalcNodeSethiUllmanNumber(const SUnit *SU) { - unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; - if (SethiUllmanNumber != 0) - return SethiUllmanNumber; - - unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; - if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) - SethiUllmanNumber = 0xffff; - else if (SU->NumSuccsLeft == 0) - // If SU does not have a use, i.e. it doesn't produce a value that would - // be consumed (e.g. store), then it terminates a chain of computation. - // Give it a small SethiUllman number so it will be scheduled right before - // its predecessors that it doesn't lengthen their live ranges. - SethiUllmanNumber = 0; - else if (SU->NumPredsLeft == 0 && - (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) - SethiUllmanNumber = 0xffff; - else { - int Extra = 0; - for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - if (I->isCtrl) continue; // ignore chain preds - SUnit *PredSU = I->Dep; - unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); - if (PredSethiUllman > SethiUllmanNumber) { - SethiUllmanNumber = PredSethiUllman; - Extra = 0; - } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) - ++Extra; - } - - SethiUllmanNumber += Extra; - } - - return SethiUllmanNumber; -} - /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all /// scheduling units. void TDRegReductionPriorityQueue::CalculateSethiUllmanNumbers() { SethiUllmanNumbers.assign(SUnits->size(), 0); for (unsigned i = 0, e = SUnits->size(); i != e; ++i) - CalcNodeSethiUllmanNumber(&(*SUnits)[i]); + CalcNodeTDSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers); } //===----------------------------------------------------------------------===// @@ -1829,16 +1898,19 @@ llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, MachineBasicBlock *BB, bool Fast) { + if (Fast) + return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, true, + new BURegReductionFastPriorityQueue()); + const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); const TargetRegisterInfo *TRI = DAG->getTarget().getRegisterInfo(); - BURegReductionPriorityQueue *priorityQueue = - new BURegReductionPriorityQueue(TII, TRI, Fast); + BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI); - ScheduleDAGRRList * scheduleDAG = - new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, Fast,priorityQueue); - priorityQueue->setScheduleDAG(scheduleDAG); - return scheduleDAG; + ScheduleDAGRRList *SD = + new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(),true,false, PQ); + PQ->setScheduleDAG(SD); + return SD; } llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, @@ -1846,6 +1918,5 @@ llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, MachineBasicBlock *BB, bool Fast) { return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, Fast, - new TDRegReductionPriorityQueue()); + new TDRegReductionPriorityQueue()); } - -- 2.34.1