[IRSim][IROutliner] Canonicalizing commutative value numbering between similarity sections.

[AndrewLitteken]

Summary

When the initial relationship between two pairs of values between similar sections is ambiguous to commutativity, arguments to the outlined functions can be passed in such that the order is incorrect, causing miscompilations. This adds a canonical mapping to each similarity section, so that we can maintain the relationship of global value numbering from one section to another.

Added Tests:
Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll
unittests/Analysis/IRSimilarityIdentifierTest.cpp - IRSimilarityCandidate:CanonicalNumbering

[AndrewLitteken]

Updating the diff for clang-format errors.

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

586

I'd sink this closer to where it's used so there's less live range to think about.

llvm/lib/Transforms/IPO/IROutliner.cpp

855

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

2015

alternatively

2017

ASSERT_EQ(x, y); will give better diagnostics when it fails than ASSERT_TRUE(x == y); does.

2049

ASSERT_NE. Also, should it check what's in the set that was found?

[AndrewLitteken]

llvm/lib/Transforms/IPO/IROutliner.cpp

855

[paquette]

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

572

break up run-on?

579

• Use a more descriptive name than A?
• Maybe createCanonicalMappingFor would be a better name?

581

sentence is kind of long, break it up?

594

more descriptive name than A?

660

doxygen comment?

667

doxygen comment?

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

759

do you need this here?

802

do we need this here?

[yroux]

Apart from the previous comments, this patch LGTM and fixes a correctness issue observed on Spec, Thanks for that

[AndrewLitteken]

Updating for comments

[paquette]

LGTM after fixing nits on comments.

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

765

Can you change this comment to explain why you're iterating over the mappings?

772

Can you explain why?

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

private:
 
   /// Global Value Numbering structures
   /// @{
   /// Stores the mapping of the value to the number assigned to it in the
   /// IRSimilarityCandidate.
   DenseMap<Value *, unsigned> ValueToNumber;
   /// Stores the mapping of the number to the value assigned this number.
   DenseMap<unsigned, Value *> NumberToValue;
+  /// Stores the mapping of a value's number to canonical numbering in the
+  /// candidate's respective similarity group.
+  DenseMap<unsigned, unsigned> NumberToCanonNum;
+  /// Stores the mapping of canonical number in the candidate's respective
+  /// similarity group to a value number.
+  DenseMap<unsigned, unsigned> CanonNumToNumber;
   /// @}
 
 public:
   /// \param StartIdx - The starting location of the region.
   /// \param Len - The length of the region.
   /// \param FirstInstIt - The starting IRInstructionData of the region.
   /// \param LastInstIt - The ending IRInstructionData of the region.
   IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
                         IRInstructionData *FirstInstIt,
                         IRInstructionData *LastInstIt);
 
   /// \param A - The first IRInstructionCandidate to compare.
   /// \param B - The second IRInstructionCandidate to compare.
   /// \returns True when every IRInstructionData in \p A is similar to every
   /// IRInstructionData in \p B.
   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<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
+                   DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB);
+
   struct OperandMapping {
     /// The IRSimilarityCandidate that holds the instruction the OperVals were
     /// pulled from.
     const IRSimilarityCandidate &IRSC;
 
     /// The operand values to be analyzed.
     ArrayRef<Value *> &OperVals;
 
public:
   /// \param A - The first IRInstructionCandidate, operand values, and current
   /// operand mappings to compare.
   /// \param B - The second IRInstructionCandidate, operand values, and current
   /// operand mappings to compare.
   /// \returns true if the IRSimilarityCandidates operands are compatible.
   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<unsigned, DenseSet<unsigned>> &ToAMapping,
+      DenseMap<unsigned, DenseSet<unsigned>> &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
   /// the start instruction of one is greater than the start instruction of the
   /// other, they overlap.
   ///
   /// \returns true if the IRSimilarityCandidates do not have overlapping
   /// instructions.
public:
   Optional<Value *> fromGVN(unsigned Num) {
     DenseMap<unsigned, Value *>::iterator VNIt = NumberToValue.find(Num);
     if (VNIt == NumberToValue.end())
       return None;
     assert(VNIt->second != nullptr && "Found value is a nullptr!");
     return VNIt->second;
   }
 
+  Optional<unsigned> getCanonicalNum(unsigned N) {
+    DenseMap<unsigned, unsigned>::iterator NCIt = NumberToCanonNum.find(N);
+    if (NCIt == NumberToCanonNum.end())
+      return None;
+    return NCIt->second;
+  }
+
+  Optional<unsigned> fromCanonicalNum(unsigned N) {
+    DenseMap<unsigned, unsigned>::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.
   bool operator<(const IRSimilarityCandidate &RHS) const {
     return getStartIdx() > RHS.getStartIdx();
   }
 
   using iterator = IRInstructionDataList::iterator;
   iterator begin() const { return iterator(front()); }
   iterator end() const { return std::next(iterator(back())); }
 };
 
+typedef DenseMap<IRSimilarityCandidate *,
+                 DenseMap<unsigned, DenseSet<unsigned>>>
+    CandidateGVNMapping;
 typedef std::vector<IRSimilarityCandidate> SimilarityGroup;
 typedef std::vector<SimilarityGroup> SimilarityGroupList;
 
 /// This class puts all the pieces of the IRInstructionData,
 /// IRInstructionMapper, IRSimilarityCandidate together.
 ///
 /// It first feeds the Module or vector of Modules into the IRInstructionMapper,
 /// and puts all the mapped instructions into a single long list of

llvm/include/llvm/Transforms/IPO/IROutliner.h

struct OutlinableRegion {
   /// Mapping the extracted argument number to the argument number in the
   /// overall function.  Since there will be inputs, such as elevated constants
   /// that are not the same in each region in a SimilarityGroup, or values that
   /// cannot be sunk into the extracted section in every region, we must keep
   /// track of which extracted argument maps to which overall argument.
   DenseMap<unsigned, unsigned> ExtractedArgToAgg;
   DenseMap<unsigned, unsigned> 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
   /// since the CodeExtractor does not recognize constants.
   DenseMap<unsigned, Constant *> AggArgToConstant;
 
   /// The global value numbers that are used as outputs for this section. Once
   /// extracted, each output will be stored to an output register.  This

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

if (!checkNumberingAndReplaceCommutative(B.IRSC.ValueToNumber,
                                            ValueNumbersA))
     return false;
 
   return true;
 }
 
 bool IRSimilarityCandidate::compareStructure(const IRSimilarityCandidate &A,
                                              const IRSimilarityCandidate &B) {
+  DenseMap<unsigned, DenseSet<unsigned>> MappingA;
+  DenseMap<unsigned, DenseSet<unsigned>> MappingB;
+  return IRSimilarityCandidate::compareStructure(A, B, MappingA, MappingB);
+}
+
+bool IRSimilarityCandidate::compareStructure(
+    const IRSimilarityCandidate &A, const IRSimilarityCandidate &B,
+    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
+    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB) {
   if (A.getLength() != B.getLength())
     return false;
 
   if (A.ValueToNumber.size() != B.ValueToNumber.size())
     return false;
 
   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<unsigned, DenseSet<unsigned>> ValueNumberMappingA;
-  DenseMap<unsigned, DenseSet<unsigned>> 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<unsigned, DenseSet<unsigned>>::iterator ValueMappingIt;
 
-  bool WasInserted;
 
   // Iterate over the instructions contained in each candidate
   unsigned SectionLength = A.getStartIdx() + A.getLength();
   for (unsigned Loc = A.getStartIdx(); Loc < SectionLength;
        ItA++, ItB++, Loc++) {
     // Make sure the instructions are similar to one another.
     if (!isClose(*ItA, *ItB))
       return false;
for (const unsigned &StartIdx : RS.StartIndices) {
     std::advance(StartIt, StartIdx);
     std::vector<IRInstructionData *>::iterator EndIt = InstrList.begin();
     std::advance(EndIt, EndIdx);
 
     CandsForRepSubstring.emplace_back(StartIdx, StringLen, *StartIt, *EndIt);
   }
 }
 
+void IRSimilarityCandidate::createCanonicalRelationFrom(
+    IRSimilarityCandidate &A,
+    DenseMap<unsigned, DenseSet<unsigned>> &ToAMapping,
+    DenseMap<unsigned, DenseSet<unsigned>> &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<unsigned> UsedGVNs;
+  // Iterate over the mappings provided from this candidate to A.
+  for (std::pair<unsigned, DenseSet<unsigned>> &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<unsigned, DenseSet<unsigned>>::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<unsigned, Value *> &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.
 ///
 /// \param [in] CandsForRepSubstring - The vector containing the
 /// IRSimilarityCandidates.
 /// \param [out] StructuralGroups - the mapping of unsigned integers to vector
 /// of IRSimilarityCandidates where each of the IRSimilarityCandidates in the
static void findCandidateStructures(
   unsigned CurrentGroupNum = 0;
   unsigned OuterGroupNum;
   DenseMap<IRSimilarityCandidate *, unsigned>::iterator CandToGroupIt;
   DenseMap<IRSimilarityCandidate *, unsigned>::iterator CandToGroupItInner;
   DenseMap<unsigned, SimilarityGroup>::iterator CurrentGroupPair;
 
   // Iterate over the candidates to determine its structural and overlapping
   // compatibility with other instructions
+  DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingA;
+  DenseMap<unsigned, DenseSet<unsigned>> ValueNumberMappingB;
   for (CandIt = CandsForRepSubstring.begin(),
       CandEndIt = CandsForRepSubstring.end();
        CandIt != CandEndIt; CandIt++) {
 
     // Determine if it has an assigned structural group already.
     CandToGroupIt = CandToGroup.find(&*CandIt);
     if (CandToGroupIt == CandToGroup.end()) {
       // If not, we assign it one, and add it to our mapping.
       std::tie(CandToGroupIt, Inserted) =
           CandToGroup.insert(std::make_pair(&*CandIt, CurrentGroupNum++));
     }
 
     // Get the structural group number from the iterator.
     OuterGroupNum = CandToGroupIt->second;
 
     // 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
     // IRSimilarityCandidates are compatible.  This is so we do not repeat pairs
     // of IRSimilarityCandidates.
     for (InnerCandIt = std::next(CandIt),
         InnerCandEndIt = CandsForRepSubstring.end();
          InnerCandIt != InnerCandEndIt; InnerCandIt++) {
 
       // We check if the inner item has a group already, if it does, we skip it.
       CandToGroupItInner = CandToGroup.find(&*InnerCandIt);
       if (CandToGroupItInner != CandToGroup.end())
         continue;
 
       // 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);
     }
   }
 }
 
 void IRSimilarityIdentifier::findCandidates(
     std::vector<IRInstructionData *> &InstrList,

llvm/lib/Transforms/IPO/IROutliner.cpp

struct OutlinableGroup {
   /// Flag for whether the \ref ArgumentTypes have been defined after the
   /// extraction of the first region.
   bool InputTypesSet = false;
 
   /// The number of input values in \ref ArgumentTypes.  Anything after this
   /// 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<unsigned, unsigned> CanonicalNumberToAggArg;
+
   /// The number of instructions that will be outlined by extracting \ref
   /// Regions.
   InstructionCost Benefit = 0;
   /// The number of added instructions needed for the outlining of the \ref
   /// Regions.
   InstructionCost Cost = 0;
 
   /// The argument that needs to be marked with the swifterr attribute.  If not
findExtractedInputToOverallInputMapping(OutlinableRegion &Region,
   // This counts the argument number in the extracted function.
   unsigned OriginalIndex = 0;
 
   // Find the mapping of the extracted arguments to the arguments for the
   // overall function. Since there may be extra arguments in the overall
   // 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<unsigned> CanonicalNumberOpt = C.getCanonicalNum(InputVal);
+    assert(CanonicalNumberOpt.hasValue() && "Canonical number not found?");
+    unsigned CanonicalNumber = CanonicalNumberOpt.getValue();
+
     Optional<Value *> InputOpt = C.fromGVN(InputVal);
     assert(InputOpt.hasValue() && "Global value number not found?");
     Value *Input = InputOpt.getValue();
 
+    DenseMap<unsigned, unsigned>::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
       // argument in the overall function.
       if (Input->isSwiftError()) {
         assert(
             !Group.SwiftErrorArgument.hasValue() &&
             "Argument already marked with swifterr for this OutlinableGroup!");
         Group.SwiftErrorArgument = TypeIndex;
       }
     }
 
     // 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<Constant>(Input)) {
+      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!");
 
+    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++;
   }
 
   // If the function type definitions for the OutlinableGroup holding the region
   // have not been set, set the length of the inputs here.  We should have the
   // same inputs for all of the different regions contained in the
   // OutlinableGroup since they are all structurally similar to one another.
CallInst *replaceCalledFunction(Module &M, OutlinableRegion &Region) {
 
   OutlinableGroup &Group = *Region.Parent;
   CallInst *Call = Region.Call;
   assert(Call && "Call to replace is nullptr?");
   Function *AggFunc = Group.OutlinedFunction;
   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);
     return Call;
   }
 
   // We have a different number of arguments than the new function, so
   // we need to use our previously mappings off extracted argument to overall

llvm/test/Transforms/IROutliner/outlining-commutative-operands-opposite-order.ll

+; 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:%.*]]
+;

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

TEST(IRSimilarityCandidate, SameStructure) {
   // Check to make sure that we have a long enough region.
   ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
   // Check that the instructions were added correctly to both vectors.
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
 
   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<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
+  SpecificBumpPtrAllocator<IRInstructionDataList> 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<unsigned>(6));
+  // Check that the instructions were added correctly to both vectors.
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  std::vector<IRInstructionData *>::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<unsigned, DenseSet<unsigned>> Mapping1;
+  DenseMap<unsigned, DenseSet<unsigned>> Mapping2;
+  ASSERT_TRUE(IRSimilarityCandidate::compareStructure(Cand1, Cand2, Mapping1,
+                                                      Mapping2));
+  IRSimilarityCandidate::createCanonicalFor(Cand1);
+  Cand2.createCanonicalRelationFrom(Cand1, Mapping1, Mapping2);
+
+  for (std::pair<unsigned, DenseSet<unsigned>> &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<unsigned>::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) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = add i32 %a, %b
                              %1 = add i32 %b, %a