[IRSim] Adding support for isomorphic predicates

[AndrewLitteken]

Summary

Some predicates, can be considered the same as long as the operands are flipped. For example, a > b gives the same result as b > a. This maps instructions in a greater than form, to their appropriate less than form, swapping the operands in the IRInstructionData only, allowing for more flexible matching.

Tests:

• llvm/test/Transforms/IROutliner/outlining-isomorphic-predicates.ll
• llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

86

Should equality and inequality also be canonicalized? Maybe your hash function can be tweaked to use an operation that's commutative specifically in that case.

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

86

Oh, I see that's being handled here: https://reviews.llvm.org/D87311

[jroelofs]

LGTM

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

135–136

Since we generally don't build with exceptions turned on, it makes more sense to talk about what's allowed/not in the function's contract, rather than mentioning that assertion failures "throw".

[AndrewLitteken]

A few things changed just enough since OperTypes was removed, so updating the diff to reflect this.

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

struct IRInstructionData : ilist_node<IRInstructionData> {
   /// The values of the operands in the Instruction.
   SmallVector<Value *, 4> OperVals;
   /// The legality of the wrapped instruction. This is informed by InstrType,
   /// and is used when checking when two instructions are considered similar.
   /// If either instruction is not legal, the instructions are automatically not
   /// considered similar.
   bool Legal;
 
+  /// This is only relevant if we are wrapping a CmpInst where we needed to
+  /// change the predicate of a compare instruction from a greater than form
+  /// to a less than form.  It is None otherwise.
+  Optional<CmpInst::Predicate> RevisedPredicate;
+
   /// Gather the information that is difficult to gather for an Instruction, or
   /// is changed. i.e. the operands of an Instruction and the Types of those
   /// operands. This extra information allows for similarity matching to make
   /// assertions that allow for more flexibility when checking for whether an
   /// Instruction performs the same operation.
   IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL);
 
+  /// Get the predicate that the compare instruction is using for hashing the
+  /// instruction. the IRInstructionData must be wrapping a CmpInst.
+  CmpInst::Predicate getPredicate() const;
+
+  /// A function that swaps the predicates to their less than form if they are
+  /// in a greater than form. Otherwise, the predicate is unchanged.
+  ///
+  /// \param CI - The comparison operation to find a consistent preidcate for.
+  /// \return the consistent comparison predicate. 
+  static CmpInst::Predicate predicateForConsistency(CmpInst *CI);
+
   /// Hashes \p Value based on its opcode, types, and operand types.
   /// Two IRInstructionData instances produce the same hash when they perform
   /// the same operation.
   ///
   /// As a simple example, consider the following instructions.
   ///
   /// \code
   /// %add1 = add i32 %x1, %y1
struct IRInstructionData : ilist_node<IRInstructionData> {
   ///
   /// \param [in] Value - The IRInstructionData instance to be hashed.
   /// \returns A hash_value of the IRInstructionData.
   friend hash_code hash_value(const IRInstructionData &ID) {
     SmallVector<Type *, 4> OperTypes;
     for (Value *V : ID.OperVals)
       OperTypes.push_back(V->getType());
 
+    if (isa<CmpInst>(ID.Inst))
+      return hash_combine(
+          hash_value(ID.Inst->getOpcode()),
+          hash_value(ID.Inst->getType()), hash_value(ID.getPredicate()),
+          hash_combine_range(OperTypes.begin(), OperTypes.end()));
     return hash_combine(
         hash_value(ID.Inst->getOpcode()), hash_value(ID.Inst->getType()),
         hash_combine_range(OperTypes.begin(), OperTypes.end()));
   }
 
   IRInstructionDataList *IDL = nullptr;
 };
 

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

 #include "llvm/Support/SuffixTree.h"
 
 using namespace llvm;
 using namespace IRSimilarity;
 
 IRInstructionData::IRInstructionData(Instruction &I, bool Legality,
                                      IRInstructionDataList &IDList)
     : Inst(&I), Legal(Legality), IDL(&IDList) {
-  // Here we collect the operands to determine whether
+  // We check for whether we have a comparison instruction.  If it is, we
+  // find the "less than" version of the predicate for consistency for
+  // comparison instructions throught the program.
+  if (CmpInst *C = dyn_cast<CmpInst>(&I)) {
+    CmpInst::Predicate Predicate = predicateForConsistency(C);
+    if (Predicate != C->getPredicate())
+      RevisedPredicate = Predicate;
+  }
+
+  // Here we collect the operands and their types for determining whether
   // the structure of the operand use matches between two different candidates.
-  for (Use &OI : I.operands())
+  for (Use &OI : I.operands()) {
+    if (isa<CmpInst>(I) && RevisedPredicate.hasValue()) {
+      // If we have a CmpInst where the predicate is reversed, it means the
+      // operands must be reversed as well.
+      OperVals.insert(OperVals.begin(), OI.get());
+      continue;
+    }
+
     OperVals.push_back(OI.get());
   }
+}
+
+CmpInst::Predicate IRInstructionData::predicateForConsistency(CmpInst *CI) {
+  switch (CI->getPredicate()) {
+  case CmpInst::FCMP_OGT:
+  case CmpInst::FCMP_UGT:
+  case CmpInst::FCMP_OGE:
+  case CmpInst::FCMP_UGE:
+  case CmpInst::ICMP_SGT:
+  case CmpInst::ICMP_UGT:
+  case CmpInst::ICMP_SGE:
+  case CmpInst::ICMP_UGE:
+    return CI->getSwappedPredicate();
+  default:
+    return CI->getPredicate();
+  }
+}
+
+CmpInst::Predicate IRInstructionData::getPredicate() const {
+  assert(isa<CmpInst>(Inst) &&
+         "Can only get a predicate from a compare instruction");
+
+  if (RevisedPredicate.hasValue())
+    return RevisedPredicate.getValue();
+  
+  return cast<CmpInst>(Inst)->getPredicate();
+}
 
 bool IRSimilarity::isClose(const IRInstructionData &A,
                            const IRInstructionData &B) {
-  return A.Legal && A.Inst->isSameOperationAs(B.Inst);
+
+  if (!A.Legal || !B.Legal)
+    return false;
+
+  // Check if we are performing the same sort of operation on the same types
+  // but not on the same values.
+  if (A.Inst->isSameOperationAs(B.Inst))
+    return true;
+
+  // If there is a predicate, this means that either there is a swapped
+  // predicate, or that the types are different, we want to make sure that
+  // the predicates are equivalent via swapping.
+  if (isa<CmpInst>(A.Inst) && isa<CmpInst>(B.Inst)) {
+
+    if (A.getPredicate() != B.getPredicate())
+      return false;
+
+    // If the predicates are the same via swap, make sure that the types are
+    // still the same.
+    auto ZippedTypes = zip(A.OperVals, B.OperVals);
+
+    return all_of(ZippedTypes, [](std::tuple<llvm::Value *, llvm::Value *> R) {
+      return std::get<0>(R)->getType() == std::get<1>(R)->getType();
+    });
+  }
+
+  return false;
 }
 
 // TODO: This is the same as the MachineOutliner, and should be consolidated
 // into the same interface.
 void IRInstructionMapper::convertToUnsignedVec(
     BasicBlock &BB, std::vector<IRInstructionData *> &InstrList,
     std::vector<unsigned> &IntegerMapping) {
   BasicBlock::iterator It = BB.begin();

llvm/test/Transforms/IROutliner/outlining-isomorphic-predicates.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -verify -iroutliner < %s | FileCheck %s
+
+; This test checks the isomorphic comparisons can be outlined together into one
+; function.
+
+; The following three function are identical, except that in the third, the
+; operand order, and predicate are swapped, meaning it is structurally the same
+; and should be outlined together.
+
+define void @outline_slt1() {
+; CHECK-LABEL: @outline_slt1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_1(i32* [[A]], i32* [[B]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp slt i32 %al, %bl
+  ret void
+}
+
+define void @outline_slt2() {
+; CHECK-LABEL: @outline_slt2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_1(i32* [[A]], i32* [[B]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp slt i32 %al, %bl
+  ret void
+}
+
+define void @outline_sgt() {
+; CHECK-LABEL: @outline_sgt(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_1(i32* [[A]], i32* [[B]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp sgt i32 %bl, %al
+  ret void
+}
+
+; This has a swapped predicate, but not swapped operands, so it cannot use
+; the same outlined function as the ones above.
+
+define void @dontoutline_sgt() {
+; CHECK-LABEL: @dontoutline_sgt(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    store i32 3, i32* [[B]], align 4
+; CHECK-NEXT:    [[AL:%.*]] = load i32, i32* [[A]], align 4
+; CHECK-NEXT:    [[BL:%.*]] = load i32, i32* [[B]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[AL]], [[BL]]
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp sgt i32 %al, %bl
+  ret void
+}
+
+; The below functions use a different kind of predicate that is not compatible
+; with the ones above, and should use a different outlined function.
+; The other difference here is that the predicate with swapped operands comes
+; first this time.
+
+define void @outline_ugt1() {
+; CHECK-LABEL: @outline_ugt1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp ugt i32 %al, %bl
+  ret void
+}
+
+define void @outline_ugt2() {
+; CHECK-LABEL: @outline_ugt2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp ugt i32 %al, %bl
+  ret void
+}
+
+define void @outline_ult() {
+; CHECK-LABEL: @outline_ult(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %a = alloca i32, align 4
+  %b = alloca i32, align 4
+  store i32 2, i32* %a, align 4
+  store i32 3, i32* %b, align 4
+  %al = load i32, i32* %a
+  %bl = load i32, i32* %b
+  %0 = icmp ult i32 %bl, %al
+  ret void
+}
+
+; CHECK: define internal void @outlined_ir_func_0(i32* [[ARG0:%.*]], i32* [[ARG1:%.*]]) #0 {
+; CHECK: entry_to_outline:
+; CHECK-NEXT:    store i32 2, i32* [[ARG0]], align 4
+; CHECK-NEXT:    store i32 3, i32* [[ARG1]], align 4
+; CHECK-NEXT:    [[AL:%.*]] = load i32, i32* [[ARG0]], align 4
+; CHECK-NEXT:    [[BL:%.*]] = load i32, i32* [[ARG1]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ugt i32 [[AL]], [[BL]]
+
+; CHECK: define internal void @outlined_ir_func_1(i32* [[ARG0:%.*]], i32* [[ARG1:%.*]]) #0 {
+; CHECK: entry_to_outline:
+; CHECK-NEXT:    store i32 2, i32* [[ARG0]], align 4
+; CHECK-NEXT:    store i32 3, i32* [[ARG1]], align 4
+; CHECK-NEXT:    [[AL:%.*]] = load i32, i32* [[ARG0]], align 4
+; CHECK-NEXT:    [[BL:%.*]] = load i32, i32* [[ARG1]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[AL]], [[BL]]

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

TEST(IRInstructionMapper, PredicateDifferentiation) {
 
   getVectors(*M, InstrList, UnsignedVec);
 
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
   ASSERT_TRUE(UnsignedVec.size() == 3);
   ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
 }
 
-// Checks that predicates with the same swapped predicate map to different
-// values.
+// Checks that predicates where that can be considered the same when the
+// operands are swapped, i.e. greater than to less than are mapped to the same
+// unsigned integer.
 TEST(IRInstructionMapper, PredicateIsomorphism) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = icmp sgt i32 %a, %b
                              %1 = icmp slt i32 %b, %a
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;
   std::vector<unsigned> UnsignedVec;
 
   getVectors(*M, InstrList, UnsignedVec);
 
   ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
   ASSERT_TRUE(UnsignedVec.size() == 3);
-  ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
+  ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
 }
 
 // Checks that the same predicate maps to the same value.
 TEST(IRInstructionMapper, PredicateSimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = icmp slt i32 %a, %b
TEST(IRSimilarityCandidate, CheckIdenticalInstructions) {
   End = InstrList.begin();
   std::advance(End, 1);
   IRSimilarityCandidate Cand1(0, 2, *Start, *End);
   IRSimilarityCandidate Cand2(0, 2, *Start, *End);
 
   ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
 }
 
+// Checks that comparison instructions are found to be similar instructions
+// when the operands are flipped and the predicate is also swapped.
+TEST(IRSimilarityCandidate, PredicateIsomorphism) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = icmp sgt i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = icmp slt i32 %a, %b
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  getVectors(*M, InstrList, UnsignedVec);
+
+
+  ASSERT_TRUE(InstrList.size() > 5);
+  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);
+
+  ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
+}
+
 // Checks that IRSimilarityCandidates wrapping these two regions of instructions
 // are able to differentiate between instructions that have different opcodes.
 TEST(IRSimilarityCandidate, CheckRegionsDifferentInstruction) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = add i32 %a, %b
                              %1 = add i32 %b, %a
TEST(IRSimilarityCandidate, DifferentStructure) {
   // 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_FALSE(longSimCandCompare(InstrList, true));
 }
 
+// Checks that comparison instructions are found to have the same structure
+// when the operands are flipped and the predicate is also swapped.
+TEST(IRSimilarityCandidate, PredicateIsomorphismStructure) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = icmp sgt i32 %a, %b
+                             %1 = add i32 %a, %b
+                             br label %bb1
+                          bb1:
+                             %2 = icmp slt i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  getVectors(*M, InstrList, UnsignedVec);
+
+  ASSERT_TRUE(InstrList.size() > 5);
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_TRUE(longSimCandCompare(InstrList, true));
+}
+
+// Checks that different predicates are counted as diferent.
+TEST(IRSimilarityCandidate, PredicateDifference) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = icmp sge i32 %a, %b
+                             %1 = add i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = icmp slt i32 %b, %a
+                             %3 = add i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<IRInstructionData *> InstrList;
+  std::vector<unsigned> UnsignedVec;
+
+  getVectors(*M, InstrList, UnsignedVec);
+
+  ASSERT_TRUE(InstrList.size() > 5);
+  ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
+
+  ASSERT_FALSE(longSimCandCompare(InstrList));
+}
+
 // Checks that the same structure is recognized between two candidates. The
 // items %a and %b are used in the same way in both sets of instructions.
 TEST(IRSimilarityCandidate, SameStructure) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = add i32 %a, %b
                              %1 = sub i32 %b, %a
for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
     unsigned InstIdx = 0;
     for (IRSimilarityCandidate &Cand : Cands) {
       ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
       InstIdx += 3;
     }
   }
 }
 
+// Check that we find instances of swapped predicate isomorphism.  That is,
+// for predicates that can be flipped, e.g. greater than to less than,
+// we can identify that instances of these different literal predicates, but are
+// the same within a single swap can be found.
+TEST(IRSimilarityIdentifier, PredicateIsomorphism) {
+  StringRef ModuleString = R"(
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = add i32 %a, %b
+                             %1 = icmp sgt i32 %b, %a
+                             br label %bb1
+                          bb1:
+                             %2 = add i32 %a, %b
+                             %3 = icmp slt i32 %a, %b
+                             ret i32 0
+                          })";
+  LLVMContext Context;
+  std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
+
+  std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
+  getSimilarities(*M, SimilarityCandidates);
+
+  ASSERT_TRUE(SimilarityCandidates.size() == 1);
+  for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
+    ASSERT_TRUE(Cands.size() == 2);
+    unsigned InstIdx = 0;
+    for (IRSimilarityCandidate &Cand : Cands) {
+      ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
+      InstIdx += 3;
+    }
+  }
+}
+
 // Checks that constants are detected as the same operand in each use in the
 // sequences of instructions.  Also checks that we can find structural
 // equivalence using constants.  In this case the 1 has the same use pattern as
 // %a.
 TEST(IRSimilarityIdentifier, ConstantMappingSimilarity) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0: