From 95f6edeff5ab6de9cf5589f662c8e7a6ba119c2c Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Sat, 4 Nov 2006 09:44:31 +0000 Subject: [PATCH] Changes to use operand constraints to process two-address instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31453 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SelectionDAG/ScheduleDAG.cpp | 13 +- lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 5 +- .../SelectionDAG/ScheduleDAGRRList.cpp | 172 +++++++++++++----- 3 files changed, 140 insertions(+), 50 deletions(-) diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index cfc27a32d54..dd968ed4544 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -126,8 +126,13 @@ void ScheduleDAG::BuildSchedUnits() { if (MainNode->isTargetOpcode()) { unsigned Opc = MainNode->getTargetOpcode(); - if (TII->isTwoAddrInstr(Opc)) - SU->isTwoAddress = true; + for (unsigned i = 0, ee = TII->getNumOperands(Opc); i != ee; ++i) { + if (TII->getOperandConstraint(Opc, i, + TargetInstrInfo::TIED_TO) != -1) { + SU->isTwoAddress = true; + break; + } + } if (TII->isCommutableInstr(Opc)) SU->isCommutable = true; } @@ -210,7 +215,7 @@ void ScheduleDAG::CalculateHeights() { /// CountResults - The results of target nodes have register or immediate /// operands first, then an optional chain, and optional flag operands (which do /// not go into the machine instrs.) -static unsigned CountResults(SDNode *Node) { +unsigned ScheduleDAG::CountResults(SDNode *Node) { unsigned N = Node->getNumValues(); while (N && Node->getValueType(N - 1) == MVT::Flag) --N; @@ -222,7 +227,7 @@ static unsigned CountResults(SDNode *Node) { /// CountOperands The inputs to target nodes have any actual inputs first, /// followed by an optional chain operand, then flag operands. Compute the /// number of actual operands that will go into the machine instr. -static unsigned CountOperands(SDNode *Node) { +unsigned ScheduleDAG::CountOperands(SDNode *Node) { unsigned N = Node->getNumOperands(); while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) --N; diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 1be9fc518e9..da8b1cddb8c 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -98,7 +98,7 @@ void ScheduleDAGList::Schedule() { // Build scheduling units. BuildSchedUnits(); - AvailableQueue->initNodes(SUnits); + AvailableQueue->initNodes(SUnitMap, SUnits); ListScheduleTopDown(); @@ -331,7 +331,8 @@ public: LatencyPriorityQueue() : Queue(latency_sort(this)) { } - void initNodes(std::vector &sunits) { + void initNodes(std::map &sumap, + std::vector &sunits) { SUnits = &sunits; // Calculate node priorities. CalculatePriorities(); diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index b37d2825bc8..3b5e2e17152 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp @@ -95,7 +95,7 @@ void ScheduleDAGRRList::Schedule() { CalculateDepths(); CalculateHeights(); - AvailableQueue->initNodes(SUnits); + AvailableQueue->initNodes(SUnitMap, SUnits); // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. if (isBottomUp) @@ -115,7 +115,7 @@ void ScheduleDAGRRList::Schedule() { EmitSchedule(); } -/// CommuteNodesToReducePressure - Is a node is two-address and commutable, and +/// CommuteNodesToReducePressure - If a node is two-address and commutable, and /// it is not the last use of its first operand, add it to the CommuteSet if /// possible. It will be commuted when it is translated to a MI. void ScheduleDAGRRList::CommuteNodesToReducePressure() { @@ -123,23 +123,38 @@ void ScheduleDAGRRList::CommuteNodesToReducePressure() { for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node. SUnit *SU = Sequence[i]; if (!SU) continue; - if (SU->isTwoAddress && SU->isCommutable) { - SDNode *OpN = SU->Node->getOperand(0).Val; - SUnit *OpSU = SUnitMap[OpN]; - if (OpSU && OperandSeen.count(OpSU) == 1) { - // Ok, so SU is not the last use of OpSU, but SU is two-address so - // it will clobber OpSU. Try to commute it if possible. - bool DoCommute = true; - for (unsigned j = 1, e = SU->Node->getNumOperands(); j != e; ++j) { - OpN = SU->Node->getOperand(j).Val; - OpSU = SUnitMap[OpN]; - if (OpSU && OperandSeen.count(OpSU) == 1) { - DoCommute = false; - break; + if (SU->isCommutable) { + unsigned Opc = SU->Node->getTargetOpcode(); + unsigned NumRes = CountResults(SU->Node); + unsigned NumOps = CountOperands(SU->Node); + for (unsigned j = 0; j != NumOps; ++j) { + if (TII->getOperandConstraint(Opc, j+NumRes, + TargetInstrInfo::TIED_TO) == -1) + continue; + + SDNode *OpN = SU->Node->getOperand(j).Val; + SUnit *OpSU = SUnitMap[OpN]; + if (OpSU && OperandSeen.count(OpSU) == 1) { + // Ok, so SU is not the last use of OpSU, but SU is two-address so + // it will clobber OpSU. Try to commute SU if no other source operands + // are live below. + bool DoCommute = true; + for (unsigned k = 0; k < NumOps; ++k) { + if (k != j) { + OpN = SU->Node->getOperand(k).Val; + OpSU = SUnitMap[OpN]; + if (OpSU && OperandSeen.count(OpSU) == 1) { + DoCommute = false; + break; + } + } } + if (DoCommute) + CommuteSet.insert(SU->Node); } - if (DoCommute) - CommuteSet.insert(SU->Node); + + // Only look at the first use&def node for now. + break; } } @@ -411,7 +426,8 @@ namespace { RegReductionPriorityQueue() : Queue(SF(this)) {} - virtual void initNodes(std::vector &sunits) {} + virtual void initNodes(std::map &sumap, + std::vector &sunits) {} virtual void releaseState() {} virtual int getSethiUllmanNumber(unsigned NodeNum) const { @@ -434,21 +450,32 @@ namespace { Queue.pop(); return V; } + + virtual bool isDUOperand(const SUnit *SU1, const SUnit *SU2) { + return false; + } }; template class VISIBILITY_HIDDEN BURegReductionPriorityQueue : public RegReductionPriorityQueue { + // SUnitMap SDNode to SUnit mapping (n -> 1). + std::map *SUnitMap; + // SUnits - The SUnits for the current graph. const std::vector *SUnits; // SethiUllmanNumbers - The SethiUllman number for each node. std::vector SethiUllmanNumbers; + const TargetInstrInfo *TII; public: - BURegReductionPriorityQueue() {} + BURegReductionPriorityQueue(const TargetInstrInfo *tii) + : TII(tii) {} - void initNodes(std::vector &sunits) { + void initNodes(std::map &sumap, + std::vector &sunits) { + SUnitMap = &sumap; SUnits = &sunits; // Add pseudo dependency edges for two-address nodes. AddPseudoTwoAddrDeps(); @@ -466,7 +493,21 @@ namespace { return SethiUllmanNumbers[NodeNum]; } + bool isDUOperand(const SUnit *SU1, const SUnit *SU2) { + unsigned Opc = SU1->Node->getTargetOpcode(); + unsigned NumRes = ScheduleDAG::CountResults(SU1->Node); + unsigned NumOps = ScheduleDAG::CountOperands(SU1->Node); + for (unsigned i = 0; i != NumOps; ++i) { + if (TII->getOperandConstraint(Opc, i+NumRes, + TargetInstrInfo::TIED_TO) == -1) + continue; + if (SU1->Node->getOperand(i).isOperand(SU2->Node)) + return true; + } + return false; + } private: + bool canClobber(SUnit *SU, SUnit *Op); void AddPseudoTwoAddrDeps(); void CalculatePriorities(); int CalcNodePriority(const SUnit *SU); @@ -475,6 +516,9 @@ namespace { template class TDRegReductionPriorityQueue : public RegReductionPriorityQueue { + // SUnitMap SDNode to SUnit mapping (n -> 1). + std::map *SUnitMap; + // SUnits - The SUnits for the current graph. const std::vector *SUnits; @@ -484,7 +528,9 @@ namespace { public: TDRegReductionPriorityQueue() {} - void initNodes(std::vector &sunits) { + void initNodes(std::map &sumap, + std::vector &sunits) { + SUnitMap = &sumap; SUnits = &sunits; // Calculate node priorities. CalculatePriorities(); @@ -563,13 +609,11 @@ bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { // as a def&use operand is preferred. if (LIsTarget && RIsTarget) { if (left->isTwoAddress && !right->isTwoAddress) { - SDNode *DUNode = left->Node->getOperand(0).Val; - if (DUNode->isOperand(right->Node)) + if (SPQ->isDUOperand(left, right)) LBonus += 2; } if (!left->isTwoAddress && right->isTwoAddress) { - SDNode *DUNode = right->Node->getOperand(0).Val; - if (DUNode->isOperand(left->Node)) + if (SPQ->isDUOperand(right, left)) RBonus += 2; } } @@ -616,32 +660,70 @@ static bool isReachable(SUnit *SU, SUnit *TargetSU) { return Reached; } -static SUnit *getDefUsePredecessor(SUnit *SU) { - SDNode *DU = SU->Node->getOperand(0).Val; - for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - if (I->second) continue; // ignore chain preds - SUnit *PredSU = I->first; - if (PredSU->Node == DU) - return PredSU; +template +bool BURegReductionPriorityQueue::canClobber(SUnit *SU, SUnit *Op) { + if (SU->isTwoAddress) { + unsigned Opc = SU->Node->getTargetOpcode(); + unsigned NumRes = ScheduleDAG::CountResults(SU->Node); + unsigned NumOps = ScheduleDAG::CountOperands(SU->Node); + for (unsigned i = 0; i != NumOps; ++i) { + if (TII->getOperandConstraint(Opc, i+NumRes, + TargetInstrInfo::TIED_TO) != -1) { + SDNode *DU = SU->Node->getOperand(i).Val; + if (Op == (*SUnitMap)[DU]) + return true; + } + } } - - // Must be flagged. - return NULL; -} - -static bool canClobber(SUnit *SU, SUnit *Op) { - if (SU->isTwoAddress) - return Op == getDefUsePredecessor(SU); return false; } + /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses /// it as a def&use operand. Add a pseudo control edge from it to the other /// node (if it won't create a cycle) so the two-address one will be scheduled /// first (lower in the schedule). template void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() { +#if 1 + for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { + SUnit *SU = (SUnit *)&((*SUnits)[i]); + if (!SU->isTwoAddress) + continue; + + SDNode *Node = SU->Node; + if (!Node->isTargetOpcode()) + continue; + + unsigned Opc = Node->getTargetOpcode(); + unsigned NumRes = ScheduleDAG::CountResults(Node); + unsigned NumOps = ScheduleDAG::CountOperands(Node); + for (unsigned j = 0; j != NumOps; ++j) { + if (TII->getOperandConstraint(Opc, j+NumRes, + TargetInstrInfo::TIED_TO) != -1) { + SDNode *DU = SU->Node->getOperand(j).Val; + SUnit *DUSU = (*SUnitMap)[DU]; + for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end(); + I != E; ++I) { + if (I->second) continue; + SUnit *SuccSU = I->first; + if (SuccSU != SU && + (!canClobber(SuccSU, DUSU) || + (!SU->isCommutable && SuccSU->isCommutable))){ + if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) { + DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum + << " to SU #" << SuccSU->NodeNum << "\n"); + if (SU->addPred(SuccSU, true)) + SU->NumChainPredsLeft++; + if (SuccSU->addSucc(SU, true)) + SuccSU->NumChainSuccsLeft++; + } + } + } + } + } + } +#else for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { SUnit *SU = (SUnit *)&((*SUnits)[i]); SDNode *Node = SU->Node; @@ -649,7 +731,7 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() { continue; if (SU->isTwoAddress) { - SUnit *DUSU = getDefUsePredecessor(SU); + SUnit *DUSU = getDefUsePredecessor(SU, TII); if (!DUSU) continue; for (SUnit::succ_iterator I = DUSU->Succs.begin(), E = DUSU->Succs.end(); @@ -657,7 +739,7 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() { if (I->second) continue; SUnit *SuccSU = I->first; if (SuccSU != SU && - (!canClobber(SuccSU, DUSU) || + (!canClobber(SuccSU, DUSU, TII) || (!SU->isCommutable && SuccSU->isCommutable))){ if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) { DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum @@ -671,6 +753,7 @@ void BURegReductionPriorityQueue::AddPseudoTwoAddrDeps() { } } } +#endif } /// CalcNodePriority - Priority is the Sethi Ullman number. @@ -858,8 +941,9 @@ void TDRegReductionPriorityQueue::CalculatePriorities() { llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, MachineBasicBlock *BB) { + const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, - new BURegReductionPriorityQueue()); + new BURegReductionPriorityQueue(TII)); } llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, -- 2.34.1