diff --git a/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h b/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h --- a/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h +++ b/llvm/include/llvm/Analysis/IRSimilarityIdentifier.h @@ -488,6 +488,12 @@ DenseMap ValueToNumber; /// Stores the mapping of the number to the value assigned this number. DenseMap NumberToValue; + /// Stores the mapping of a value's number to canonical numbering in the + /// candidate's respective similarity group. + DenseMap NumberToCanonNum; + /// Stores the mapping of canonical number in the candidate's respective + /// similarity group to a value number. + DenseMap CanonNumToNumber; /// @} public: @@ -506,13 +512,27 @@ static bool isSimilar(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B); - /// \param A - The first IRInstructionCandidate to compare. - /// \param B - The second IRInstructionCandidate to compare. + /// \param [in] A - The first IRInstructionCandidate to compare. + /// \param [in] B - The second IRInstructionCandidate to compare. /// \returns True when every IRInstructionData in \p A is structurally similar /// to \p B. static bool compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B); + /// \param [in] A - The first IRInstructionCandidate to compare. + /// \param [in] B - The second IRInstructionCandidate to compare. + /// \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 + /// candidate \p B to candidate \A. + /// \returns True when every IRInstructionData in \p A is structurally similar + /// to \p B. + static bool + compareStructure(const IRSimilarityCandidate &A, + const IRSimilarityCandidate &B, + DenseMap> &ValueNumberMappingA, + DenseMap> &ValueNumberMappingB); + struct OperandMapping { /// The IRSimilarityCandidate that holds the instruction the OperVals were /// pulled from. @@ -549,6 +569,33 @@ static bool compareCommutativeOperandMapping(OperandMapping A, OperandMapping B); + /// Create a mapping from the value numbering to a different separate set of + /// numbers. This will serve as a guide for relating one candidate to another. + /// The canonical number gives use the ability identify which global value + /// number in one candidate relates to the global value number in the other. + /// + /// \param [in, out] CurrCand - The IRSimilarityCandidate to create a + /// canonical numbering for. + static void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand); + + /// 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. + /// + /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a + /// canonical numbering from. + /// \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> &ToSourceMapping, + DenseMap> &FromSourceMapping); + /// Compare the start and end indices of the two IRSimilarityCandidates for /// whether they overlap. If the start instruction of one /// IRSimilarityCandidate is less than the end instruction of the other, and @@ -611,6 +658,32 @@ return VNIt->second; } + /// Find the canonical number from the global value number \p N stored in the + /// candidate. + /// + /// \param N - The global value number to find the canonical number for. + /// \returns An optional containing the value, and None if it could not be + /// found. + Optional getCanonicalNum(unsigned N) { + DenseMap::iterator NCIt = NumberToCanonNum.find(N); + if (NCIt == NumberToCanonNum.end()) + return None; + return NCIt->second; + } + + /// Find the global value number from the canonical number \p N stored in the + /// candidate. + /// + /// \param N - The canonical number to find the global vlaue number for. + /// \returns An optional containing the value, and None if it could not be + /// found. + Optional fromCanonicalNum(unsigned N) { + DenseMap::iterator CNIt = CanonNumToNumber.find(N); + if (CNIt == CanonNumToNumber.end()) + return None; + return CNIt->second; + } + /// \param RHS -The IRSimilarityCandidate to compare against /// \returns true if the IRSimilarityCandidate is occurs after the /// IRSimilarityCandidate in the program. @@ -623,6 +696,9 @@ iterator end() const { return std::next(iterator(back())); } }; +typedef DenseMap>> + CandidateGVNMapping; typedef std::vector SimilarityGroup; typedef std::vector SimilarityGroupList; diff --git a/llvm/include/llvm/Transforms/IPO/IROutliner.h b/llvm/include/llvm/Transforms/IPO/IROutliner.h --- a/llvm/include/llvm/Transforms/IPO/IROutliner.h +++ b/llvm/include/llvm/Transforms/IPO/IROutliner.h @@ -86,6 +86,11 @@ DenseMap ExtractedArgToAgg; DenseMap AggArgToExtracted; + /// Marks whether we need to change the order of the arguments when mapping + /// the old extracted function call to the new aggregate outlined function + /// call. + bool ChangedArgOrder = false; + /// Mapping of the argument number in the deduplicated function /// to a given constant, which is used when creating the arguments to the call /// to the newly created deduplicated function. This is handled separately diff --git a/llvm/lib/Analysis/IRSimilarityIdentifier.cpp b/llvm/lib/Analysis/IRSimilarityIdentifier.cpp --- a/llvm/lib/Analysis/IRSimilarityIdentifier.cpp +++ b/llvm/lib/Analysis/IRSimilarityIdentifier.cpp @@ -565,6 +565,15 @@ bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A, const IRSimilarityCandidate &B) { + DenseMap> MappingA; + DenseMap> MappingB; + return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB); +} + +bool IRSimilarityCandidate::compareStructure( + const IRSimilarityCandidate &A, const IRSimilarityCandidate &B, + DenseMap> &ValueNumberMappingA, + DenseMap> &ValueNumberMappingB) { if (A.getLength() != B.getLength()) return false; @@ -574,15 +583,12 @@ iterator ItA = A.begin(); iterator ItB = B.begin(); - // These sets create a create a mapping between the values in one candidate - // to values in the other candidate. If we create a set with one element, - // and that same element maps to the original element in the candidate - // we have a good mapping. - DenseMap> ValueNumberMappingA; - DenseMap> ValueNumberMappingB; + // These ValueNumber Mapping sets create a create a mapping between the values + // in one candidate to values in the other candidate. If we create a set with + // one element, and that same element maps to the original element in the + // candidate we have a good mapping. DenseMap>::iterator ValueMappingIt; - bool WasInserted; // Iterate over the instructions contained in each candidate unsigned SectionLength = A.getStartIdx() + A.getLength(); @@ -605,6 +611,7 @@ unsigned InstValA = A.ValueToNumber.find(IA)->second; unsigned InstValB = B.ValueToNumber.find(IB)->second; + bool WasInserted; // Ensure that the mappings for the instructions exists. std::tie(ValueMappingIt, WasInserted) = ValueNumberMappingA.insert( std::make_pair(InstValA, DenseSet({InstValB}))); @@ -739,6 +746,78 @@ } } +void IRSimilarityCandidate::createCanonicalRelationFrom( + IRSimilarityCandidate &SourceCand, + DenseMap> &ToSourceMapping, + DenseMap> &FromSourceMapping) { + assert(SourceCand.CanonNumToNumber.size() != 0 && + "Base canonical relationship is empty!"); + assert(SourceCand.NumberToCanonNum.size() != 0 && + "Base canonical relationship is empty!"); + + assert(CanonNumToNumber.size() == 0 && "Canonical Relationship is non-empty"); + assert(NumberToCanonNum.size() == 0 && "Canonical Relationship is non-empty"); + + DenseSet UsedGVNs; + // Iterate over the mappings provided from this candidate to A. + for (std::pair> &GVNMapping : ToSourceMapping) { + unsigned SourceGVN = GVNMapping.first; + + assert(GVNMapping.second.size() != 0 && "Possible GVNs is 0!"); + + unsigned ResultGVN; + // We need special handling if we have more than one potential value. + if (GVNMapping.second.size() > 1) { + bool Found = false; + for (unsigned Val : GVNMapping.second) { + // We make sure the target value number hasn't already been reserved. + if (UsedGVNs.find(Val) != UsedGVNs.end()) + continue; + + // We make sure that the opposite mapping is still consistent. + DenseMap>::iterator It = + FromSourceMapping.find(Val); + + if (It->second.find(SourceGVN) == It->second.end()) + continue; + + // We pick the first item that satisfies these conditions. + Found = true; + ResultGVN = Val; + break; + } + + assert(Found && "Could not find matching value for source GVN"); + + } else + ResultGVN = *GVNMapping.second.begin(); + + // Whatever GVN is found, we mark it as used. + UsedGVNs.insert(ResultGVN); + + unsigned CanonNum = *SourceCand.getCanonicalNum(ResultGVN); + CanonNumToNumber.insert(std::make_pair(CanonNum, SourceGVN)); + NumberToCanonNum.insert(std::make_pair(SourceGVN, CanonNum)); + } +} + +void IRSimilarityCandidate::createCanonicalMappingFor( + IRSimilarityCandidate &CurrCand) { + assert(CurrCand.CanonNumToNumber.size() == 0 && + "Canonical Relationship is non-empty"); + assert(CurrCand.NumberToCanonNum.size() == 0 && + "Canonical Relationship is non-empty"); + + unsigned CanonNum = 0; + // Iterate over the value numbers found, the order does not matter in this + // case. + for (std::pair &NumToVal : CurrCand.NumberToValue) { + CurrCand.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum)); + CurrCand.CanonNumToNumber.insert(std::make_pair(CanonNum, NumToVal.first)); + CanonNum++; + } +} + /// From the list of IRSimilarityCandidates, perform a comparison between each /// IRSimilarityCandidate to determine if there are overlapping /// IRInstructionData, or if they do not have the same structure. @@ -774,6 +853,8 @@ // Iterate over the candidates to determine its structural and overlapping // compatibility with other instructions + DenseMap> ValueNumberMappingA; + DenseMap> ValueNumberMappingB; for (CandIt = CandsForRepSubstring.begin(), CandEndIt = CandsForRepSubstring.end(); CandIt != CandEndIt; CandIt++) { @@ -792,9 +873,11 @@ // Check if we already have a list of IRSimilarityCandidates for the current // structural group. Create one if one does not exist. CurrentGroupPair = StructuralGroups.find(OuterGroupNum); - if (CurrentGroupPair == StructuralGroups.end()) + if (CurrentGroupPair == StructuralGroups.end()) { + IRSimilarityCandidate::createCanonicalMappingFor(*CandIt); std::tie(CurrentGroupPair, Inserted) = StructuralGroups.insert( std::make_pair(OuterGroupNum, SimilarityGroup({*CandIt}))); + } // Iterate over the IRSimilarityCandidates following the current // IRSimilarityCandidate in the list to determine whether the two @@ -811,11 +894,15 @@ // Otherwise we determine if they have the same structure and add it to // vector if they match. - SameStructure = - IRSimilarityCandidate::compareStructure(*CandIt, *InnerCandIt); + ValueNumberMappingA.clear(); + ValueNumberMappingB.clear(); + SameStructure = IRSimilarityCandidate::compareStructure( + *CandIt, *InnerCandIt, ValueNumberMappingA, ValueNumberMappingB); if (!SameStructure) continue; + InnerCandIt->createCanonicalRelationFrom(*CandIt, ValueNumberMappingA, + ValueNumberMappingB); CandToGroup.insert(std::make_pair(&*InnerCandIt, OuterGroupNum)); CurrentGroupPair->second.push_back(*InnerCandIt); } diff --git a/llvm/lib/Transforms/IPO/IROutliner.cpp b/llvm/lib/Transforms/IPO/IROutliner.cpp --- a/llvm/lib/Transforms/IPO/IROutliner.cpp +++ b/llvm/lib/Transforms/IPO/IROutliner.cpp @@ -87,6 +87,10 @@ /// index in ArgumentTypes is an output argument. unsigned NumAggregateInputs = 0; + /// The mapping of the canonical numbering of the values in outlined sections + /// to specific arguments. + DenseMap CanonicalNumberToAggArg; + /// The number of instructions that will be outlined by extracting \ref /// Regions. InstructionCost Benefit = 0; @@ -665,11 +669,22 @@ // function to account for the extracted constants, we have two different // counters as we find extracted arguments, and as we come across overall // arguments. + + // Additionally, in our first pass, for the first extracted function, + // we find argument locations for the canonical value numbering. This + // numbering overrides any discovered location for the extracted code. for (unsigned InputVal : InputGVNs) { + Optional CanonicalNumberOpt = C.getCanonicalNum(InputVal); + assert(CanonicalNumberOpt.hasValue() && "Canonical number not found?"); + unsigned CanonicalNumber = CanonicalNumberOpt.getValue(); + Optional InputOpt = C.fromGVN(InputVal); assert(InputOpt.hasValue() && "Global value number not found?"); Value *Input = InputOpt.getValue(); + DenseMap::iterator AggArgIt = + Group.CanonicalNumberToAggArg.find(CanonicalNumber); + if (!Group.InputTypesSet) { Group.ArgumentTypes.push_back(Input->getType()); // If the input value has a swifterr attribute, make sure to mark the @@ -685,17 +700,34 @@ // Check if we have a constant. If we do add it to the overall argument // number to Constant map for the region, and continue to the next input. if (Constant *CST = dyn_cast(Input)) { - Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST)); + if (AggArgIt != Group.CanonicalNumberToAggArg.end()) + Region.AggArgToConstant.insert(std::make_pair(AggArgIt->second, CST)); + else { + Group.CanonicalNumberToAggArg.insert( + std::make_pair(CanonicalNumber, TypeIndex)); + Region.AggArgToConstant.insert(std::make_pair(TypeIndex, CST)); + } TypeIndex++; continue; } // It is not a constant, we create the mapping from extracted argument list - // to the overall argument list. + // to the overall argument list, using the canonical location, if it exists. assert(ArgInputs.count(Input) && "Input cannot be found!"); - Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex)); - Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex)); + if (AggArgIt != Group.CanonicalNumberToAggArg.end()) { + if (OriginalIndex != AggArgIt->second) + Region.ChangedArgOrder = true; + Region.ExtractedArgToAgg.insert( + std::make_pair(OriginalIndex, AggArgIt->second)); + Region.AggArgToExtracted.insert( + std::make_pair(AggArgIt->second, OriginalIndex)); + } else { + Group.CanonicalNumberToAggArg.insert( + std::make_pair(CanonicalNumber, TypeIndex)); + Region.ExtractedArgToAgg.insert(std::make_pair(OriginalIndex, TypeIndex)); + Region.AggArgToExtracted.insert(std::make_pair(TypeIndex, OriginalIndex)); + } OriginalIndex++; TypeIndex++; } @@ -821,9 +853,10 @@ assert(AggFunc && "Function to replace with is nullptr?"); // If the arguments are the same size, there are not values that need to be - // made argument, or different output registers to handle. We can simply - // replace the called function in this case. - if (AggFunc->arg_size() == Call->arg_size()) { + // made into an argument, the argument ordering has not been change, or + // different output registers to handle. We can simply replace the called + // function in this case. + if (!Region.ChangedArgOrder && AggFunc->arg_size() == Call->arg_size()) { LLVM_DEBUG(dbgs() << "Replace call to " << *Call << " with call to " << *AggFunc << " with same number of arguments\n"); Call->setCalledFunction(AggFunc); diff --git a/llvm/test/Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll b/llvm/test/Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll @@ -0,0 +1,40 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals --include-generated-funcs +; RUN: opt -S -iroutliner -ir-outlining-no-cost < %s | FileCheck %s + +; This is a test to ensure that when the first instruction is a commutative +; instruction, but the order of operands is reversed, we pass the arguments +; in the correct order, such that we do not use the wrong arguments +; later on in the computation. + +define void @fish(i32 %0, i32 %1, i32 %2) { +entry: + %3 = add nsw i32 %0, %1 + %4 = sub nsw i32 %1, %2 + %5 = sub nsw i32 %0, %2 + ret void +} + +define void @turtle(i32 %0, i32 %1, i32 %2) { + %4 = add nsw i32 %1, %0 + %5 = sub nsw i32 %1, %2 + %6 = sub nsw i32 %0, %2 + ret void +} +; CHECK-LABEL: @fish( +; CHECK-NEXT: entry: +; CHECK-NEXT: call void @outlined_ir_func_0(i32 [[TMP0:%.*]], i32 [[TMP1:%.*]], i32 [[TMP2:%.*]]) +; CHECK-NEXT: ret void +; +; +; CHECK-LABEL: @turtle( +; CHECK-NEXT: call void @outlined_ir_func_0(i32 [[TMP0:%.*]], i32 [[TMP1:%.*]], i32 [[TMP2:%.*]]) +; CHECK-NEXT: ret void +; +; +; CHECK: @outlined_ir_func_0(i32 [[TMP0:%.*]], i32 [[TMP1:%.*]], i32 [[TMP2:%.*]]) +; CHECK: entry_to_outline: +; CHECK-NEXT: [[TMP3:%.*]] = add nsw i32 [[TMP0]], [[TMP1]] +; CHECK-NEXT: [[TMP4:%.*]] = sub nsw i32 [[TMP1]], [[TMP2]] +; CHECK-NEXT: [[TMP5:%.*]] = sub nsw i32 [[TMP0]], [[TMP2]] +; CHECK-NEXT: br label [[ENTRY_AFTER_OUTLINE_EXITSTUB:%.*]] +; diff --git a/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp b/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp --- a/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp +++ b/llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp @@ -1986,6 +1986,70 @@ ASSERT_TRUE(longSimCandCompare(InstrList, true)); } +// Checks that the canonical numbering between two candidates matches the found +// mapping between two candidates. +TEST(IRSimilarityCandidate, CanonicalNumbering) { + StringRef ModuleString = R"( + define i32 @f(i32 %a, i32 %b) { + bb0: + %0 = add i32 %a, %b + %1 = sub i32 %b, %a + ret i32 0 + bb1: + %2 = add i32 %a, %b + %3 = sub i32 %b, %a + ret i32 0 + })"; + LLVMContext Context; + std::unique_ptr M = makeLLVMModule(Context, ModuleString); + + std::vector InstrList; + std::vector UnsignedVec; + + SpecificBumpPtrAllocator InstDataAllocator; + SpecificBumpPtrAllocator IDLAllocator; + IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator); + getVectors(*M, Mapper, InstrList, UnsignedVec); + + // Check to make sure that we have a long enough region. + ASSERT_EQ(InstrList.size(), static_cast(6)); + // Check that the instructions were added correctly to both vectors. + ASSERT_EQ(InstrList.size(), UnsignedVec.size()); + + std::vector::iterator Start, End; + + Start = InstrList.begin(); + End = InstrList.begin(); + + std::advance(End, 1); + IRSimilarityCandidate Cand1(0, 2, *Start, *End); + + Start = InstrList.begin(); + End = InstrList.begin(); + + std::advance(Start, 3); + std::advance(End, 4); + IRSimilarityCandidate Cand2(3, 2, *Start, *End); + DenseMap> Mapping1; + DenseMap> Mapping2; + ASSERT_TRUE(IRSimilarityCandidate::compareStructure(Cand1, Cand2, Mapping1, + Mapping2)); + IRSimilarityCandidate::createCanonicalMappingFor(Cand1); + Cand2.createCanonicalRelationFrom(Cand1, Mapping1, Mapping2); + + for (std::pair> &P : Mapping2) { + unsigned Source = P.first; + + ASSERT_TRUE(Cand2.getCanonicalNum(Source).hasValue()); + unsigned Canon = *Cand2.getCanonicalNum(Source); + ASSERT_TRUE(Cand1.fromCanonicalNum(Canon).hasValue()); + unsigned Dest = *Cand1.fromCanonicalNum(Canon); + + DenseSet::iterator It = P.second.find(Dest); + ASSERT_NE(It, P.second.end()); + } +} + // Checks that the same structure is recognized between two candidates. While // the input names are reversed, they still perform the same overall operation. TEST(IRSimilarityCandidate, DifferentNameSameStructure) {