[IRSim] Letting gep instructions be legal for similarity identification.

[AndrewLitteken]

Summary

GetElementPtr instructions require the extra check that all operands after the first must only be constants and be exactly the same to be considered similar.

Tests are found in unittests/Analysis/IRSimilarityIdentifierTest.cpp.

[jroelofs]

LGTM

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

47

auto *GEP is probably appropriate here, if you want, since the type name gets repeated.

57

Likewise, I'd probably auto these, since the type of the iterator isn't super important to make visible. I think this is a grey area when it comes to community preference, so either way is fine, and I'll leave it up to you.

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

struct InstructionClassification
     // We exclude all exception handling cases since they are so context
     // dependent.
     InstrType visitLandingPadInst(LandingPadInst &LPI) { return Illegal; }
     InstrType visitFuncletPadInst(FuncletPadInst &FPI) { return Illegal; }
     // DebugInfo should be included in the regions, but should not be
     // analyzed for similarity as it has no bearing on the outcome of the
     // program.
     InstrType visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII) { return Invisible; }
-    // TODO: Handle GetElementPtrInsts
-    InstrType visitGetElementPtrInst(GetElementPtrInst &GEPI) {
-      return Illegal;
-    }
     // TODO: Handle specific intrinsics.
     InstrType visitIntrinsicInst(IntrinsicInst &II) { return Illegal; }
     // TODO: Handle CallInsts.
     InstrType visitCallInst(CallInst &CI) { return Illegal; }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitInvokeInst(InvokeInst &II) { return Illegal; }
     // TODO: We do not current handle similarity that changes the control flow.
     InstrType visitCallBrInst(CallBrInst &CBI) { return Illegal; }

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

 bool IRSimilarity::isClose(const IRInstructionData &A,
                            const IRInstructionData &B) {
 
   // 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 false;
 
+  // Since any GEP Instruction operands after the first operand cannot be
+  // defined by a register, we must make sure that the operands after the first
+  // are the same in the two instructions
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(A.Inst)) {
+    GetElementPtrInst *OtherGEP = cast<GetElementPtrInst>(B.Inst);
+
+    // If the instructions do not have the same inbounds restrictions, we do
+    // not consider them the same.
+    if (GEP->isInBounds() != OtherGEP->isInBounds())
+      return false;
+
+    detail::zippy<detail::zip_shortest, iterator_range<Use *>,
+                  iterator_range<Use *>>
+        ZippedOperands = zip(GEP->indices(), OtherGEP->indices());
+
+    detail::zippy<detail::zip_shortest, iterator_range<Use *>,
+                  iterator_range<Use *>>::iterator ZIt = ZippedOperands.begin();
+
+    // We increment here since we do not care about the first instruction,
+    // we only care about the following operands since they must be the
+    // exact same to be considered similar.
+    return std::all_of(++ZIt, ZippedOperands.end(),
+                       [](std::tuple<llvm::Use &, llvm::Use &> R) {
+                         return std::get<0>(R) == std::get<1>(R);
+                       });
+  }
+
   return true;
 }
 
 // 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> &UnsignedVec) {

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

TEST(IRInstructionMapper, AllocaIllegal) {
   std::vector<unsigned> UnsignedVec;
 
   getVectors(*M, InstrList, UnsignedVec);
 
   ASSERT_EQ(InstrList.size(), UnsignedVec.size());
   ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
 }
 
-// Checks that an getelementptr instruction is mapped to be illegal.  There is
-// extra checking required for the parameters if a getelementptr has more than
-// two operands.
-TEST(IRInstructionMapper, GetElementPtrIllegal) {
+// Checks that an getelementptr instruction is mapped to be legal.  And that
+// the operands in getelementpointer instructions are the exact same after the
+// first element operand, which only requires the same type.
+TEST(IRInstructionMapper, GetElementPtrSameEndOperands) {
   StringRef ModuleString = R"(
     %struct.RT = type { i8, [10 x [20 x i32]], i8 }
     %struct.ST = type { i32, double, %struct.RT }
-    define i32 @f(%struct.ST* %s, i32 %a, i32 %b) {
+    define i32 @f(%struct.ST* %s, i64 %a, i64 %b) {
     bb0:
-       %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1
+       %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0
+       %1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %b, i32 0
        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_EQ(InstrList.size(), UnsignedVec.size());
-  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Check that when the operands in getelementpointer instructions are not the
+// exact same after the first element operand, the instructions are mapped to
+// different values.
+TEST(IRInstructionMapper, GetElementPtrDifferentEndOperands) {
+  StringRef ModuleString = R"(
+    %struct.RT = type { i8, [10 x [20 x i32]], i8 }
+    %struct.ST = type { i32, double, %struct.RT }
+    define i32 @f(%struct.ST* %s, i64 %a, i64 %b) {
+    bb0:
+       %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0
+       %1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %b, i32 2
+       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_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Check that when the operands in getelementpointer instructions are not the
+// same initial base type, each instruction is mapped to a different value.
+TEST(IRInstructionMapper, GetElementPtrDifferentBaseType) {
+  StringRef ModuleString = R"(
+    %struct.RT = type { i8, [10 x [20 x i32]], i8 }
+    %struct.ST = type { i32, double, %struct.RT }
+    define i32 @f(%struct.ST* %s, %struct.RT* %r, i64 %a, i64 %b) {
+    bb0:
+       %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a
+       %1 = getelementptr inbounds %struct.RT, %struct.RT* %r, i64 %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_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Check that when the operands in getelementpointer instructions do not have
+// the same inbounds modifier, they are not counted as the same.
+TEST(IRInstructionMapper, GetElementPtrDifferentInBounds) {
+  StringRef ModuleString = R"(
+    %struct.RT = type { i8, [10 x [20 x i32]], i8 }
+    %struct.ST = type { i32, double, %struct.RT }
+    define i32 @f(%struct.ST* %s, %struct.RT* %r, i64 %a, i64 %b) {
+    bb0:
+       %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0
+       %1 = getelementptr %struct.ST, %struct.ST* %s, i64 %b, i32 0
+       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_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
 }
 
 // Checks that a call instruction is mapped to be illegal.  We have to perform
 // extra checks to ensure that both the name and function type are the same.
 TEST(IRInstructionMapper, CallIllegal) {
   StringRef ModuleString = R"(
                           declare i32 @f1(i32, i32)
                           define i32 @f(i32 %a, i32 %b) {