Index: include/llvm/CodeGen/ScheduleDAG.h =================================================================== --- include/llvm/CodeGen/ScheduleDAG.h +++ include/llvm/CodeGen/ScheduleDAG.h @@ -43,6 +43,8 @@ /// SDep - Scheduling dependency. This represents one direction of an /// edge in the scheduling DAG. class SDep { + friend struct DenseMapInfo; + public: /// Kind - These are the different kinds of scheduling dependencies. enum Kind { @@ -258,6 +260,10 @@ SmallVector Preds; // All sunit predecessors. SmallVector Succs; // All sunit successors. + // Fast lookup for preds. + SmallDenseMap PredDepIndices; + SmallDenseMap PredUnitCounts; + typedef SmallVectorImpl::iterator pred_iterator; typedef SmallVectorImpl::iterator succ_iterator; typedef SmallVectorImpl::const_iterator const_pred_iterator; @@ -499,6 +505,31 @@ llvm_unreachable("Invalid dependency kind!"); } + /// Specialize DenseMapInfo for SDep. + template <> struct DenseMapInfo { + static inline SDep getEmptyKey() { + return SDep(DenseMapInfo::getEmptyKey(), SDep::Data, 0); + } + static inline SDep getTombstoneKey() { + return SDep(DenseMapInfo::getTombstoneKey(), SDep::Data, 0); + } + static inline unsigned getHashValue(const SDep &D) { + typedef std::pair, unsigned> PairTy; + switch (D.Dep.getInt()) { + case SDep::Data: + case SDep::Anti: + case SDep::Output: + return DenseMapInfo::getHashValue({D.Dep, D.Contents.Reg}); + case SDep::Order: + return DenseMapInfo::getHashValue({D.Dep, D.Contents.OrdKind}); + } + llvm_unreachable("Invalid dependency kind!"); + } + static inline bool isEqual(const SDep &LHS, const SDep &RHS) { + return LHS.overlaps(RHS); + } + }; + //// getSUnit - Return the SUnit to which this edge points. inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); } Index: lib/CodeGen/ScheduleDAG.cpp =================================================================== --- lib/CodeGen/ScheduleDAG.cpp +++ lib/CodeGen/ScheduleDAG.cpp @@ -63,33 +63,47 @@ /// not already. It also adds the current node as a successor of the /// specified node. bool SUnit::addPred(const SDep &D, bool Required) { + int &PredUnitCount = PredUnitCounts[D.getSUnit()]; + if (!Required && PredUnitCount > 0) + // Zero-latency weak edges may be added purely for heuristic ordering. + // Don't add them if another kind of edge already exists. + return false; + + + auto PredIndexIAndInserted = PredDepIndices.insert({D, Preds.size()}); + int PredIndex = PredIndexIAndInserted.first->second; + bool IndexInserted = PredIndexIAndInserted.second; + // If this node already has this dependence, don't add a redundant one. - for (SmallVectorImpl::iterator I = Preds.begin(), E = Preds.end(); - I != E; ++I) { - // Zero-latency weak edges may be added purely for heuristic ordering. Don't - // add them if another kind of edge already exists. - if (!Required && I->getSUnit() == D.getSUnit()) - return false; - if (I->overlaps(D)) { - // Extend the latency if needed. Equivalent to removePred(I) + addPred(D). - if (I->getLatency() < D.getLatency()) { - SUnit *PredSU = I->getSUnit(); - // Find the corresponding successor in N. - SDep ForwardD = *I; - ForwardD.setSUnit(this); - for (SmallVectorImpl::iterator II = PredSU->Succs.begin(), - EE = PredSU->Succs.end(); II != EE; ++II) { - if (*II == ForwardD) { - II->setLatency(D.getLatency()); - break; - } + if (!IndexInserted) { + assert(PredUnitCount > 0 && + "Can't have a zero count for this unit but found an existing dep!"); + SDep &ExistingD = Preds[PredIndex]; + assert(ExistingD.overlaps(D) && "Mapped to a non-overlapping dep!"); + + // Extend the latency if needed. Equivalent to removePred(I) + addPred(D). + if (ExistingD.getLatency() < D.getLatency()) { + SUnit *PredSU = ExistingD.getSUnit(); + // Find the corresponding successor in N. + SDep ForwardD = ExistingD; + ForwardD.setSUnit(this); + for (SmallVectorImpl::iterator II = PredSU->Succs.begin(), + EE = PredSU->Succs.end(); + II != EE; ++II) { + if (*II == ForwardD) { + II->setLatency(D.getLatency()); + break; } - I->setLatency(D.getLatency()); } - return false; + ExistingD.setLatency(D.getLatency()); } + return false; } - // Now add a corresponding succ to N. + + // Otherwise add the pred and a corresponding succ to N. + Preds.push_back(D); + ++PredUnitCount; + SDep P = D; P.setSUnit(this); SUnit *N = D.getSUnit(); @@ -118,7 +132,6 @@ ++N->NumSuccsLeft; } } - Preds.push_back(D); N->Succs.push_back(P); if (P.getLatency() != 0) { this->setDepthDirty(); @@ -132,47 +145,59 @@ /// the specified node. void SUnit::removePred(const SDep &D) { // Find the matching predecessor. - for (SmallVectorImpl::iterator I = Preds.begin(), E = Preds.end(); - I != E; ++I) - if (*I == D) { - // Find the corresponding successor in N. - SDep P = D; - P.setSUnit(this); - SUnit *N = D.getSUnit(); - SmallVectorImpl::iterator Succ = std::find(N->Succs.begin(), - N->Succs.end(), P); - assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!"); - N->Succs.erase(Succ); - Preds.erase(I); - // Update the bookkeeping. - if (P.getKind() == SDep::Data) { - assert(NumPreds > 0 && "NumPreds will underflow!"); - assert(N->NumSuccs > 0 && "NumSuccs will underflow!"); - --NumPreds; - --N->NumSuccs; - } - if (!N->isScheduled) { - if (D.isWeak()) - --WeakPredsLeft; - else { - assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!"); - --NumPredsLeft; - } - } - if (!isScheduled) { - if (D.isWeak()) - --N->WeakSuccsLeft; - else { - assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!"); - --N->NumSuccsLeft; - } - } - if (P.getLatency() != 0) { - this->setDepthDirty(); - N->setHeightDirty(); - } - return; + auto PredIndexI = PredDepIndices.find(D); + if (PredIndexI == PredDepIndices.end()) + return; + + // Find the corresponding successor in N. + SDep P = D; + P.setSUnit(this); + SUnit *N = D.getSUnit(); + SmallVectorImpl::iterator Succ = + std::find(N->Succs.begin(), N->Succs.end(), P); + assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!"); + N->Succs.erase(Succ); + + // Nuke the pred. + int PredIndex = PredIndexI->second; + Preds.erase(Preds.begin() + PredIndex); + PredDepIndices.erase(PredIndexI); + // To avoid random hops in the PredDepIndices table and constant hashing, we + // just walk the table and decrement every index above the one just removed. + for (auto &IndexPair : PredDepIndices) + if (IndexPair.second > PredIndex) + --IndexPair.second; + int &PredUnitCount = PredUnitCounts[D.getSUnit()]; + --PredUnitCount; + assert(PredUnitCount >= 0 && "Cannot have negative counts for an SUnit!"); + + // Update the bookkeeping. + if (P.getKind() == SDep::Data) { + assert(NumPreds > 0 && "NumPreds will underflow!"); + assert(N->NumSuccs > 0 && "NumSuccs will underflow!"); + --NumPreds; + --N->NumSuccs; + } + if (!N->isScheduled) { + if (D.isWeak()) + --WeakPredsLeft; + else { + assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!"); + --NumPredsLeft; + } + } + if (!isScheduled) { + if (D.isWeak()) + --N->WeakSuccsLeft; + else { + assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!"); + --N->NumSuccsLeft; } + } + if (P.getLatency() != 0) { + this->setDepthDirty(); + N->setHeightDirty(); + } } void SUnit::setDepthDirty() { @@ -306,8 +331,12 @@ if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth) BestI = I; } - if (BestI != Preds.begin()) + if (BestI != Preds.begin()) { + int &BestIndex = PredDepIndices[*BestI]; + int &BeginIndex = PredDepIndices[*Preds.begin()]; + std::swap(BeginIndex, BestIndex); std::swap(*Preds.begin(), *BestI); + } } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)