Index: llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp =================================================================== --- llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp +++ llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp @@ -2657,15 +2657,159 @@ Value *PromotedOperand) const; }; +class PhiNodeSet; + +/// An iterator for PhiNodeSet. +class PhiNodeSetIterator { + PhiNodeSet * const Set; + size_t CurrentIndex = 0; + +public: + /// The constructor. Start should point to either a valid element, or be equal + /// to the size of the underlying SmallVector of the PhiNodeSet. + PhiNodeSetIterator(PhiNodeSet * const Set, size_t Start); + PHINode * operator*() const; + PhiNodeSetIterator& operator++(); + bool operator==(const PhiNodeSetIterator &RHS) const; + bool operator!=(const PhiNodeSetIterator &RHS) const; +}; + +/// Keeps a set of PHINodes. +/// +/// This is a minimal set implementation for a specific use case: +/// It is very fast when there are very few elements, but also provides good +/// performance when there are many. It is similar to SmallPtrSet, but also +/// provides iteration by insertion order, which is deterministic and stable +/// across runs. It is also similar to SmallSetVector, but provides removing +/// elements in O(1) time. This is achieved by not actually removing the element +/// from the underlying vector, so comes at the cost of using more memory, but +/// that is fine, since PhiNodeSets are used as short lived objects. +class PhiNodeSet { + friend class PhiNodeSetIterator; + + using MapType = SmallDenseMap; + using iterator = PhiNodeSetIterator; + + /// Keeps the elements in the order of their insertion in the underlying + /// vector. To achieve constant time removal, it never deletes any element. + SmallVector NodeList; + + /// Keeps the elements in the underlying set implementation. This (and not the + /// NodeList defined above) is the source of truth on whether an element + /// is actually in the collection. + MapType NodeMap; + + /// Points to the first valid (not deleted) element when the set is not empty + /// and the value is not zero. Equals to the size of the underlying vector + /// when the set is empty. When the value is 0, as in the beginning, the + /// first element may or may not be valid. + size_t FirstValidElement = 0; + +public: + /// Inserts a new element to the collection. + /// \returns true if the element is actually added, i.e. was not in the + /// collection before the operation. + bool insert(PHINode *Ptr) { + if (NodeMap.insert(std::make_pair(Ptr, NodeList.size())).second) { + NodeList.push_back(Ptr); + return true; + } + return false; + } + + /// Removes the element from the collection. + /// \returns whether the element is actually removed, i.e. was in the + /// collection before the operation. + bool erase(PHINode *Ptr) { + auto it = NodeMap.find(Ptr); + if (it != NodeMap.end()) { + NodeMap.erase(Ptr); + SkipRemovedElements(FirstValidElement); + return true; + } + return false; + } + + /// Removes all elements and clears the collection. + void clear() { + NodeMap.clear(); + NodeList.clear(); + FirstValidElement = 0; + } + + /// \returns an iterator that will iterate the elements in the order of + /// insertion. + iterator begin() { + if (FirstValidElement == 0) + SkipRemovedElements(FirstValidElement); + return PhiNodeSetIterator(this, FirstValidElement); + } + + /// \returns an iterator that points to the end of the collection. + iterator end() { return PhiNodeSetIterator(this, NodeList.size()); } + + /// Returns the number of elements in the collection. + size_t size() const { + return NodeMap.size(); + } + + /// \returns 1 if the given element is in the collection, and 0 if otherwise. + size_t count(PHINode *Ptr) const { + return NodeMap.count(Ptr); + } + +private: + /// Updates the CurrentIndex so that it will point to a valid element. + /// + /// If the element of NodeList at CurrentIndex is valid, it does not + /// change it. If there are no more valid elements, it updates CurrentIndex + /// to point to the end of the NodeList. + void SkipRemovedElements(size_t &CurrentIndex) { + while (CurrentIndex < NodeList.size()) { + auto it = NodeMap.find(NodeList[CurrentIndex]); + // If the element has been deleted and added again later, NodeMap will + // point to a different index, so CurrentIndex will still be invalid. + if (it != NodeMap.end() && it->second == CurrentIndex) + break; + ++CurrentIndex; + } + } +}; + +PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *const Set, size_t Start) + : Set(Set), CurrentIndex(Start) {} + +PHINode * PhiNodeSetIterator::operator*() const { + assert(CurrentIndex < Set->NodeList.size() && + "PhiNodeSet access out of range"); + return Set->NodeList[CurrentIndex]; +} + +PhiNodeSetIterator& PhiNodeSetIterator::operator++() { + assert(CurrentIndex < Set->NodeList.size() && + "PhiNodeSet access out of range"); + ++CurrentIndex; + Set->SkipRemovedElements(CurrentIndex); + return *this; +} + +bool PhiNodeSetIterator::operator==(const PhiNodeSetIterator &RHS) const { + return CurrentIndex == RHS.CurrentIndex; +} + +bool PhiNodeSetIterator::operator!=(const PhiNodeSetIterator &RHS) const { + return CurrentIndex != RHS.CurrentIndex; +} + /// Keep track of simplification of Phi nodes. /// Accept the set of all phi nodes and erase phi node from this set /// if it is simplified. class SimplificationTracker { DenseMap Storage; const SimplifyQuery &SQ; - // Tracks newly created Phi nodes. We use a SetVector to get deterministic - // order when iterating over the set in MatchPhiSet. - SmallSetVector AllPhiNodes; + // Tracks newly created Phi nodes. The elements are iterated by insertion + // order. + PhiNodeSet AllPhiNodes; // Tracks newly created Select nodes. SmallPtrSet AllSelectNodes; @@ -2697,7 +2841,7 @@ Put(PI, V); PI->replaceAllUsesWith(V); if (auto *PHI = dyn_cast(PI)) - AllPhiNodes.remove(PHI); + AllPhiNodes.erase(PHI); if (auto *Select = dyn_cast(PI)) AllSelectNodes.erase(Select); PI->eraseFromParent(); @@ -2720,11 +2864,11 @@ assert(Get(To) == To && "Replacement PHI node is already replaced."); Put(From, To); From->replaceAllUsesWith(To); - AllPhiNodes.remove(From); + AllPhiNodes.erase(From); From->eraseFromParent(); } - SmallSetVector& newPhiNodes() { return AllPhiNodes; } + PhiNodeSet& newPhiNodes() { return AllPhiNodes; } void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); } @@ -2969,7 +3113,7 @@ /// Matcher tracks the matched Phi nodes. bool MatchPhiNode(PHINode *PHI, PHINode *Candidate, SmallSetVector &Matcher, - SmallSetVector &PhiNodesToMatch) { + PhiNodeSet &PhiNodesToMatch) { SmallVector WorkList; Matcher.insert({ PHI, Candidate }); WorkList.push_back({ PHI, Candidate }); @@ -3018,11 +3162,12 @@ /// Returns false if this matching fails and creation of new Phi is disabled. bool MatchPhiSet(SimplificationTracker &ST, bool AllowNewPhiNodes, unsigned &PhiNotMatchedCount) { - // Use a SetVector for Matched to make sure we do replacements (ReplacePhi) - // in a deterministic order below. + // Matched and PhiNodesToMatch iterate their elements in a deterministic + // order, so the replacements (ReplacePhi) are also done in a deterministic + // order. SmallSetVector Matched; SmallPtrSet WillNotMatch; - SmallSetVector &PhiNodesToMatch = ST.newPhiNodes(); + PhiNodeSet &PhiNodesToMatch = ST.newPhiNodes(); while (PhiNodesToMatch.size()) { PHINode *PHI = *PhiNodesToMatch.begin(); @@ -3057,7 +3202,7 @@ // Just remove all seen values in matcher. They will not match anything. PhiNotMatchedCount += WillNotMatch.size(); for (auto *P : WillNotMatch) - PhiNodesToMatch.remove(P); + PhiNodesToMatch.erase(P); } return true; }