Index: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h =================================================================== --- llvm/include/llvm/Analysis/IRSimilarityIdentifier.h +++ llvm/include/llvm/Analysis/IRSimilarityIdentifier.h @@ -700,6 +700,8 @@ /// \param [in] A - The first IRInstructionCandidate to compare. /// \param [in] B - The second IRInstructionCandidate to compare. + /// \param [in,out] OneToOne - A mapping of value numbers from candidate + /// \p A to candidate \B using the structure of the original instructions. /// \param [in,out] ValueNumberMappingA - A mapping of value numbers from /// candidate \p A to candidate \B. /// \param [in,out] ValueNumberMappingB - A mapping of value numbers from @@ -709,6 +711,7 @@ static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B, + DenseMap &OneToOne, DenseMap> &ValueNumberMappingA, DenseMap> &ValueNumberMappingB); @@ -815,7 +818,8 @@ /// the canonical ordering in \p SourceCand. These are defined based on the /// found mappings in \p ToSourceMapping and \p FromSourceMapping. Both of /// these relationships should have the same information, just in opposite - /// directions. + /// directions. This has some amount of non-determinism, as there is no + /// fallback if a two pairs GVNs match one another. /// /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a /// canonical numbering from. @@ -827,6 +831,30 @@ IRSimilarityCandidate &SourceCand, DenseMap> &ToSourceMapping, DenseMap> &FromSourceMapping); + + /// Create a mapping for the value numbering of the calling + /// IRSimilarityCandidate, to a different separate set of numbers, based on + /// the canonical ordering in \p SourceCand. These are defined based on the + /// found mappings in \p ToSourceMapping and \p FromSourceMapping. Both of + /// these relationships should have the same information, just in opposite + /// directions. Uses the \p OneToOne mapping from target candidate to \p + /// SourceCand GVNs to determine the mapping first for values with multiple + /// mappings. This mapping is created by the ordering of operands in the + /// instruction they are first seen in the candidates. + /// + /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a + /// canonical numbering from. + /// \param [in,out] OneToOne - A mapping of value numbers from candidate + /// \p A to candidate \B using the structure of the original instructions. + /// \param ToSourceMapping - The mapping of value numbers from this candidate + /// to \p SourceCand. + /// \param FromSourceMapping - The mapping of value numbers from \p SoureCand + /// to this candidate. + void createCanonicalRelationFrom( + IRSimilarityCandidate &SourceCand, + DenseMap &OneToOne, + DenseMap> &ToSourceMapping, + DenseMap> &FromSourceMapping); /// \param [in,out] BBSet - The set to track the basic blocks. void getBasicBlocks(DenseSet &BBSet) const { Index: llvm/lib/Analysis/IRSimilarityIdentifier.cpp =================================================================== --- llvm/lib/Analysis/IRSimilarityIdentifier.cpp +++ llvm/lib/Analysis/IRSimilarityIdentifier.cpp @@ -730,7 +730,9 @@ const IRSimilarityCandidate &B) { DenseMap> MappingA; DenseMap> MappingB; - return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB); + DenseMap OneToOne; + return IRSimilarityCandidate::compareStructure(A, B, OneToOne, MappingA, + MappingB); } typedef detail::zippy &, @@ -738,8 +740,13 @@ ArrayRef &> ZippedRelativeLocationsT; +typedef detail::zippy &, + ArrayRef &> + ZippedOperValsT; + bool IRSimilarityCandidate::compareStructure( const IRSimilarityCandidate &A, const IRSimilarityCandidate &B, + DenseMap &OneToOne, DenseMap> &ValueNumberMappingA, DenseMap> &ValueNumberMappingB) { if (A.getLength() != B.getLength()) @@ -790,6 +797,13 @@ std::make_pair(InstValB, DenseSet({InstValA}))); if (!WasInserted && !ValueMappingIt->second.contains(InstValA)) return false; + + ZippedOperValsT ZippedOperVals = zip(OperValsA, OperValsB); + for (const std::tuple &OperPair : ZippedOperVals) { + unsigned GVNSource = A.ValueToNumber.find(std::get<0>(OperPair))->second; + unsigned GVNTarg = B.ValueToNumber.find(std::get<1>(OperPair))->second; + OneToOne.insert(std::make_pair(GVNTarg, GVNSource)); + } // We have different paths for commutative instructions and non-commutative // instructions since commutative instructions could allow multiple mappings @@ -957,6 +971,16 @@ IRSimilarityCandidate &SourceCand, DenseMap> &ToSourceMapping, DenseMap> &FromSourceMapping) { + DenseMap OneToOne; + createCanonicalRelationFrom(SourceCand, OneToOne, ToSourceMapping, + FromSourceMapping); +} + +void IRSimilarityCandidate::createCanonicalRelationFrom( + IRSimilarityCandidate &SourceCand, + DenseMap &OneToOne, + DenseMap> &ToSourceMapping, + DenseMap> &FromSourceMapping) { assert(SourceCand.CanonNumToNumber.size() != 0 && "Base canonical relationship is empty!"); assert(SourceCand.NumberToCanonNum.size() != 0 && @@ -981,7 +1005,24 @@ // here to ensure a one-to-one mapping. if (GVNMapping.second.size() > 1) { bool Found = false; + DenseMap::iterator OTOIt = OneToOne.find(SourceGVN); + + // If possible use the One-to-One mapping from the original instructions + // to determine the mapping between global value numbers. + if (OTOIt != OneToOne.end()) { + DenseMap>::iterator It = + FromSourceMapping.find(OTOIt->second); + + if (It->second.contains(SourceGVN)) { + Found = true; + ResultGVN = OTOIt->second; + } + } + for (unsigned Val : GVNMapping.second) { + if (Found) + break; + // We make sure the target value number hasn't already been reserved. if (UsedGVNs.contains(Val)) continue; @@ -1102,6 +1143,7 @@ // compatibility with other instructions DenseMap> ValueNumberMappingA; DenseMap> ValueNumberMappingB; + DenseMap OneToOne; for (CandIt = CandsForRepSubstring.begin(), CandEndIt = CandsForRepSubstring.end(); CandIt != CandEndIt; CandIt++) { @@ -1143,13 +1185,15 @@ // vector if they match. ValueNumberMappingA.clear(); ValueNumberMappingB.clear(); + OneToOne.clear(); SameStructure = IRSimilarityCandidate::compareStructure( - *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB); + *CandIt, *InnerCandIt, OneToOne, ValueNumberMappingA, + ValueNumberMappingB); if (!SameStructure) continue; - InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA, - ValueNumberMappingB); + InnerCandIt->createCanonicalRelationFrom( + *CandIt, OneToOne, ValueNumberMappingA, ValueNumberMappingB); CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum)); CurrentGroupPair->second.push_back(*InnerCandIt); }