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

[AndrewLitteken]

Summary

Here we let non-intrinsic calls be considered legal and valid for similarity only if the call is not indirect, and has a name.

For two calls to be considered similar, they must have the same name, the same function types, and the same set of parameters, including tail calls and calling conventions.

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

[jroelofs]

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

142

Maybe you ought to have a test that exercises the indirect call case, since getCalledFunction() will return nullptr for that.

Might also be useful to define a short helper function that extracts the name, since you'll be repeating the same logic twice for A/B.

[AndrewLitteken]

Helper functions and nullptr checking for Call Instructions.

[jroelofs]

LGTM

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

52

static StringRef

146

could sink the assert into the helper, which dedupes this a bit more.

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

933

same what?

llvm/include/llvm/Analysis/IRSimilarityIdentifier.h

for (Value *V : ID.OperVals)
       OperTypes.push_back(V->getType());
 
     if (isa<CmpInst>(ID.Inst))
       return llvm::hash_combine(
           llvm::hash_value(ID.Inst->getOpcode()),
           llvm::hash_value(ID.Inst->getType()),
           llvm::hash_value(ID.getPredicate()),
           llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
+    else if (CallInst *CI = dyn_cast<CallInst>(ID.Inst))
+      return llvm::hash_combine(
+          llvm::hash_value(ID.Inst->getOpcode()),
+          llvm::hash_value(ID.Inst->getType()),
+          llvm::hash_value(CI->getCalledFunction()->getName().str()),
+          llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
     return llvm::hash_combine(
         llvm::hash_value(ID.Inst->getOpcode()),
         llvm::hash_value(ID.Inst->getType()),
         llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
   }
 
   IRInstructionDataList *IDL = nullptr;
 };
struct InstructionClassification
     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 specific intrinsics.
     InstrType visitIntrinsicInst(IntrinsicInst &II) { return Illegal; }
-    // TODO: Handle CallInsts.
-    InstrType visitCallInst(CallInst &CI) { return Illegal; }
+    // We only allow call instructions where the function has a name and
+    // is not an indirect call.
+    InstrType visitCallInst(CallInst &CI) {
+      Function *F = CI.getCalledFunction();
+      if (!F || CI.isIndirectCall() || !F->hasName())
+        return Illegal;
+      return Legal;
+    }
     // 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; }
     // TODO: Handle interblock similarity.
     InstrType visitTerminator(Instruction &I) { return Illegal; }
     InstrType visitInstruction(Instruction &I) { return Legal; }
   };

llvm/lib/Analysis/IRSimilarityIdentifier.cpp

if (isa<CmpInst>(I) && RevisedPredicate.hasValue()) {
       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:
assert(isa<CmpInst>(Inst) &&
          "Can only get a predicate from a compare instruction");
 
   if (RevisedPredicate.hasValue())
     return RevisedPredicate.getValue();
   
   return cast<CmpInst>(Inst)->getPredicate();
 }
 
+static StringRef getCalledFunctionName(CallInst &CI) {
+  assert(CI.getCalledFunction() != nullptr && "Called Function is nullptr?");
+
+  return CI.getCalledFunction()->getName();
+}
+
 bool IRSimilarity::isClose(const IRInstructionData &A,
                            const IRInstructionData &B) {
 
   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 (auto *GEP = dyn_cast<GetElementPtrInst>(A.Inst)) {
     // 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);
                        });
   }
 
+  // If the instructions are functions, we make sure that the function name is
+  // the same.  We already know that the types are since is isSameOperationAs is
+  // true.
+  if (isa<CallInst>(A.Inst) && isa<CallInst>(B.Inst)) {
+    CallInst *CIA = cast<CallInst>(A.Inst);
+    CallInst *CIB = cast<CallInst>(B.Inst);
+    if (getCalledFunctionName(*CIA).compare(getCalledFunctionName(*CIB)) != 0)
+      return false;
+  }
+
   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> &IntegerMapping) {

llvm/test/Transforms/IROutliner/illegal-calls.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -verify -iroutliner -ir-outlining-no-cost < %s | FileCheck %s
 
 ; This test checks that we do not outline calls.  Special calls, such as
 ; indirect or nameless calls require extra handling to ensure that there
 ; are no inconsistencies when outlining and consolidating regions.
 
 declare void @f1(i32*, i32*);
 
 define void @outline_constants1() {
 ; CHECK-LABEL: @outline_constants1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    call void @outlined_ir_func_1(i32* [[A]], i32* [[B]], i32* [[C]])
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    store i32 3, i32* [[B]], align 4
+; CHECK-NEXT:    store i32 4, i32* [[C]], align 4
 ; CHECK-NEXT:    call void @f1(i32* [[A]], i32* [[B]])
 ; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]], i32* [[C]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %c = alloca i32, align 4
   store i32 2, i32* %a, align 4
   store i32 3, i32* %b, align 4
   store i32 4, i32* %c, align 4
   call void @f1(i32* %a, i32* %b)
   %al = load i32, i32* %a
   %bl = load i32, i32* %b
   %cl = load i32, i32* %c
   ret void
 }
 
 define void @outline_constants2() {
 ; CHECK-LABEL: @outline_constants2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 4
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    call void @outlined_ir_func_1(i32* [[A]], i32* [[B]], i32* [[C]])
+; CHECK-NEXT:    store i32 2, i32* [[A]], align 4
+; CHECK-NEXT:    store i32 3, i32* [[B]], align 4
+; CHECK-NEXT:    store i32 4, i32* [[C]], align 4
 ; CHECK-NEXT:    call void @f1(i32* [[A]], i32* [[B]])
 ; CHECK-NEXT:    call void @outlined_ir_func_0(i32* [[A]], i32* [[B]], i32* [[C]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = alloca i32, align 4
   %b = alloca i32, align 4
   %c = alloca i32, align 4

llvm/unittests/Analysis/IRSimilarityIdentifierTest.cpp

TEST(IRInstructionMapper, GetElementPtrDifferentInBounds) {
   IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
   getVectors(*M, Mapper, 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) {
+// Checks that indirect call instructions are mapped to be illegal since we
+// cannot guarantee the same function in two different cases.
+TEST(IRInstructionMapper, CallsIllegalIndirect) {
+  StringRef ModuleString = R"(
+                          define i32 @f(void()* %func) {
+                          bb0:
+                             call void %func()
+                             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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(0));
+}
+
+// Checks that a call instruction is mapped to be legal.  Here we check that
+// a call with the same name, and same types are mapped to the same
+// value.
+TEST(IRInstructionMapper, CallsSameTypeSameName) {
   StringRef ModuleString = R"(
                           declare i32 @f1(i32, i32)
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = call i32 @f1(i32 %a, i32 %b)
+                             %1 = call i32 @f1(i32 %a, i32 %b)
                              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);
 
   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]);
+}
+
+// Here we check that a calls with different names, but the same arguments types
+// are mapped to different value.
+TEST(IRInstructionMapper, CallsSameArgTypeDifferentName) {
+  StringRef ModuleString = R"(
+                          declare i32 @f1(i32, i32)
+                          declare i32 @f2(i32, i32)
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = call i32 @f1(i32 %a, i32 %b)
+                             %1 = call i32 @f2(i32 %a, i32 %b)
+                             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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Here we check that a calls with different names, and different arguments
+// types are mapped to different value.
+TEST(IRInstructionMapper, CallsDifferentArgTypeDifferentName) {
+  StringRef ModuleString = R"(
+                          declare i32 @f1(i32, i32)
+                          declare i32 @f2(i32)
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = call i32 @f1(i32 %a, i32 %b)
+                             %1 = call i32 @f2(i32 %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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Here we check that calls with different names, and different return
+// types are mapped to different value.
+TEST(IRInstructionMapper, CallsDifferentReturnTypeDifferentName) {
+  StringRef ModuleString = R"(
+                          declare i64 @f1(i32, i32)
+                          declare i32 @f2(i32, i32)
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = call i64 @f1(i32 %a, i32 %b)
+                             %1 = call i32 @f2(i32 %a, i32 %b)
+                             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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Here we check that calls with the same name, types, and parameters map to the
+// same unsigned integer.
+TEST(IRInstructionMapper, CallsSameParameters) {
+  StringRef ModuleString = R"(
+                          declare i32 @f1(i32, i32)
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = tail call fastcc i32 @f1(i32 %a, i32 %b)
+                             %1 = tail call fastcc i32 @f1(i32 %a, i32 %b)
+                             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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Here we check that calls with different tail call settings are mapped to
+// different values.
+TEST(IRInstructionMapper, CallsDifferentTails) {
+  StringRef ModuleString = R"(
+                          declare i32 @f1(i32, i32)
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = tail call i32 @f1(i32 %a, i32 %b)
+                             %1 = call i32 @f1(i32 %a, i32 %b)
+                             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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
+}
+
+// Here we check that calls with different calling convention settings are
+// mapped to different values.
+TEST(IRInstructionMapper, CallsDifferentCallingConventions) {
+  StringRef ModuleString = R"(
+                          declare i32 @f1(i32, i32)
+                          define i32 @f(i32 %a, i32 %b) {
+                          bb0:
+                             %0 = call fastcc i32 @f1(i32 %a, i32 %b)
+                             %1 = call i32 @f1(i32 %a, i32 %b)
+                             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);
+
+  ASSERT_EQ(InstrList.size(), UnsignedVec.size());
+  ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
+  ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
 }
 
 // Checks that an invoke instruction is mapped to be illegal. Invoke
 // instructions are considered to be illegal because of the change in the
 // control flow that is currently not recognized.
 TEST(IRInstructionMapper, InvokeIllegal) {
   StringRef ModuleString = R"(
                           define i32 @f(i8 *%gep1, i32 %b) {

 // Check the length of adding two illegal instructions one after th other.  We
 // should find that only one element is added for each illegal range.
 TEST(IRInstructionMapper, RepeatedIllegalLength) {
   StringRef ModuleString = R"(
                           define i32 @f(i32 %a, i32 %b) {
                           bb0:
                              %0 = add i32 %a, %b
                              %1 = mul i32 %a, %b
-                             %2 = call i32 @f(i32 %a, i32 %b)
-                             %3 = call i32 @f(i32 %a, i32 %b)
+                             %2 = alloca i32
+                             %3 = alloca i32
                              %4 = add i32 %a, %b
                              %5 = mul i32 %a, %b
                              ret i32 0
                           })";
   LLVMContext Context;
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
 
   std::vector<IRInstructionData *> InstrList;