Index: llvm/include/llvm/Analysis/IRSimilarityIdentifier.h =================================================================== --- llvm/include/llvm/Analysis/IRSimilarityIdentifier.h +++ 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,12 +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); + static bool + compareStructure(const IRSimilarityCandidate &A, + const IRSimilarityCandidate &B, + DenseMap> &ValueNumberMappingA, + DenseMap> &ValueNumberMappingB); struct OperandMapping { /// The IRSimilarityCandidate that holds the instruction the OperVals were @@ -549,6 +570,32 @@ 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 + /// so that we can identify which global value number in on candidate + /// relates to which number in the other. + /// + /// \param [in, out] A - The IRSimilarityCandidate to create a canonical + /// numbering for. + static void createCanonicalFor(IRSimilarityCandidate &A); + + /// Create a mapping for the value numbering of the calling + /// IRSimilarityCandidate, to a different separate set of numbers, based on + /// the canonical ordering in \A, and the found mappings in \p ToAMapping and + /// \p FromAMapping. Both of these relationships should have the same + /// information, just in opposite directions. + /// + /// \param [in, out] A - The IRSimilarityCandidate to create a canonical + /// numbering from. + /// \param ToAMapping - The mapping of value numbers from this candidate to \p + /// A. + /// \param ToAMapping - The mapping of value numbers from \p A to this + /// candidate. + void createCanonicalRelationFrom( + IRSimilarityCandidate &A, + DenseMap> &ToAMapping, + DenseMap> &FromAMapping); + /// 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,20 @@ return VNIt->second; } + Optional getCanonicalNum(unsigned N) { + DenseMap::iterator NCIt = NumberToCanonNum.find(N); + if (NCIt == NumberToCanonNum.end()) + return None; + return NCIt->second; + } + + 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 +684,9 @@ iterator end() const { return std::next(iterator(back())); } }; +typedef DenseMap>> + CandidateGVNMapping; typedef std::vector SimilarityGroup; typedef std::vector SimilarityGroupList; Index: llvm/include/llvm/Transforms/IPO/IROutliner.h =================================================================== --- llvm/include/llvm/Transforms/IPO/IROutliner.h +++ 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 Index: llvm/lib/Analysis/IRSimilarityIdentifier.cpp =================================================================== --- llvm/lib/Analysis/IRSimilarityIdentifier.cpp +++ 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,14 @@ 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; + bool WasInserted; + + // 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(); @@ -739,6 +747,79 @@ } } +void IRSimilarityCandidate::createCanonicalRelationFrom( + IRSimilarityCandidate &A, + DenseMap> &ToAMapping, + DenseMap> &FromAMapping) { + assert(A.CanonNumToNumber.size() != 0 && + "Base canonical relationship is empty!"); + assert(A.NumberToCanonNum.size() != 0 && + "Base canonical relationship is empty!"); + + assert(this->CanonNumToNumber.size() == 0 && + "Canonical Relationship is non-empty"); + assert(this->NumberToCanonNum.size() == 0 && + "Canonical Relationship is non-empty"); + + DenseSet UsedGVNs; + // Iterate over the mappings provided from this candidate to A. + for (std::pair> &GVNMapping : ToAMapping) { + 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 = + FromAMapping.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 = *A.getCanonicalNum(ResultGVN); + this->CanonNumToNumber.insert(std::make_pair(CanonNum, SourceGVN)); + this->NumberToCanonNum.insert(std::make_pair(SourceGVN, CanonNum)); + } +} + +void IRSimilarityCandidate::createCanonicalFor(IRSimilarityCandidate &A) { + assert(A.CanonNumToNumber.size() == 0 && + "Canonical Relationship is non-empty"); + assert(A.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 : A.NumberToValue) { + A.NumberToCanonNum.insert(std::make_pair(NumToVal.first, CanonNum)); + A.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 +855,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 +875,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::createCanonicalFor(*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 +896,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); } Index: llvm/lib/Transforms/IPO/IROutliner.cpp =================================================================== --- llvm/lib/Transforms/IPO/IROutliner.cpp +++ llvm/lib/Transforms/IPO/IROutliner.cpp @@ -84,6 +84,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; @@ -584,11 +588,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 @@ -604,17 +619,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++; } @@ -740,9 +772,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 argument, the arugment 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); Index: llvm/test/Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll =================================================================== --- /dev/null +++ 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:%.*]] +; \ No newline at end of file Index: llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp =================================================================== --- llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp +++ 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_TRUE(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::createCanonicalFor(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_TRUE(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) {