llvm/unittests/IR/StructuralHashTest.cpp

   1 //===- llvm/unittest/IR/StructuralHashTest.cpp ----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/IR/StructuralHash.h"
  10 #include "llvm/AsmParser/Parser.h"
  11 #include "llvm/IR/Module.h"
  12 #include "llvm/Support/SourceMgr.h"
  13 #include "gmock/gmock-matchers.h"
  14 #include "gtest/gtest.h"
  15
  16 #include <memory>
  17
  18 using namespace llvm;
  19
  20 namespace {
  21
  22 using testing::Contains;
  23 using testing::Key;
  24 using testing::Pair;
  25 using testing::SizeIs;
  26
  27 std::unique_ptr<Module> parseIR(LLVMContext &Context, const char *IR) {
  28   SMDiagnostic Err;
  29   std::unique_ptr<Module> M = parseAssemblyString(IR, Err, Context);
  30   if (!M)
  31     Err.print("StructuralHashTest", errs());
  32   return M;
  33 }
  34
  35 TEST(StructuralHashTest, Empty) {
  36   LLVMContext Ctx;
  37   std::unique_ptr<Module> M1 = parseIR(Ctx, "");
  38   std::unique_ptr<Module> M2 = parseIR(Ctx, "");
  39   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
  40 }
  41
  42 TEST(StructuralHashTest, Basic) {
  43   LLVMContext Ctx;
  44   std::unique_ptr<Module> M0 = parseIR(Ctx, "");
  45   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f() { ret void }");
  46   std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f() { ret void }");
  47   std::unique_ptr<Module> M3 = parseIR(Ctx, "@g = global i32 2");
  48   std::unique_ptr<Module> M4 = parseIR(Ctx, "@g = global i32 2");
  49   EXPECT_NE(StructuralHash(*M0), StructuralHash(*M1));
  50   EXPECT_NE(StructuralHash(*M0), StructuralHash(*M3));
  51   EXPECT_NE(StructuralHash(*M1), StructuralHash(*M3));
  52   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
  53   EXPECT_EQ(StructuralHash(*M3), StructuralHash(*M4));
  54 }
  55
  56 TEST(StructuralHashTest, BasicFunction) {
  57   LLVMContext Ctx;
  58   std::unique_ptr<Module> M = parseIR(Ctx, "define void @f() {\n"
  59                                            "  ret void\n"
  60                                            "}\n"
  61                                            "define void @g() {\n"
  62                                            "  ret void\n"
  63                                            "}\n"
  64                                            "define i32 @h(i32 %i) {\n"
  65                                            "  ret i32 %i\n"
  66                                            "}\n");
  67   EXPECT_EQ(StructuralHash(*M->getFunction("f")),
  68             StructuralHash(*M->getFunction("g")));
  69   EXPECT_NE(StructuralHash(*M->getFunction("f")),
  70             StructuralHash(*M->getFunction("h")));
  71 }
  72
  73 TEST(StructuralHashTest, Declaration) {
  74   LLVMContext Ctx;
  75   std::unique_ptr<Module> M0 = parseIR(Ctx, "");
  76   std::unique_ptr<Module> M1 = parseIR(Ctx, "declare void @f()");
  77   std::unique_ptr<Module> M2 = parseIR(Ctx, "@g = external global i32");
  78   EXPECT_EQ(StructuralHash(*M0), StructuralHash(*M1));
  79   EXPECT_EQ(StructuralHash(*M0), StructuralHash(*M2));
  80 }
  81
  82 TEST(StructuralHashTest, GlobalType) {
  83   LLVMContext Ctx;
  84   std::unique_ptr<Module> M1 = parseIR(Ctx, "@g = global i32 1");
  85   std::unique_ptr<Module> M2 = parseIR(Ctx, "@g = global float 1.0");
  86   EXPECT_NE(StructuralHash(*M1), StructuralHash(*M2));
  87 }
  88
  89 TEST(StructuralHashTest, Function) {
  90   LLVMContext Ctx;
  91   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f() { ret void }");
  92   std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f(i32) { ret void }");
  93   EXPECT_NE(StructuralHash(*M1), StructuralHash(*M2));
  94 }
  95
  96 TEST(StructuralHashTest, FunctionRetType) {
  97   LLVMContext Ctx;
  98   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f() { ret void }");
  99   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i32 @f() { ret i32 0 }");
 100   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 101   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 102 }
 103
 104 TEST(StructuralHashTest, InstructionOpCode) {
 105   LLVMContext Ctx;
 106   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f(ptr %p) {\n"
 107                                             "  %a = load i32, ptr %p\n"
 108                                             "  ret void\n"
 109                                             "}\n");
 110   std::unique_ptr<Module> M2 =
 111       parseIR(Ctx, "define void @f(ptr %p) {\n"
 112                    "  %a = getelementptr i8, ptr %p, i32 1\n"
 113                    "  ret void\n"
 114                    "}\n");
 115   EXPECT_NE(StructuralHash(*M1), StructuralHash(*M2));
 116 }
 117
 118 TEST(StructuralHashTest, InstructionSubType) {
 119   LLVMContext Ctx;
 120   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f(ptr %p) {\n"
 121                                             "  %a = load i32, ptr %p\n"
 122                                             "  ret void\n"
 123                                             "}\n");
 124   std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f(ptr %p) {\n"
 125                                             "  %a = load i64, ptr %p\n"
 126                                             "  ret void\n"
 127                                             "}\n");
 128   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 129   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 130 }
 131
 132 TEST(StructuralHashTest, InstructionType) {
 133   LLVMContext Ctx;
 134   std::unique_ptr<Module> M1 = parseIR(Ctx, "define void @f(ptr %p) {\n"
 135                                             "  %1 = load i32, ptr %p\n"
 136                                             "  ret void\n"
 137                                             "}\n");
 138   std::unique_ptr<Module> M2 = parseIR(Ctx, "define void @f(ptr %p) {\n"
 139                                             "  %1 = load float, ptr %p\n"
 140                                             "  ret void\n"
 141                                             "}\n");
 142   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 143   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 144 }
 145
 146 TEST(StructuralHashTest, IgnoredMetadata) {
 147   LLVMContext Ctx;
 148   std::unique_ptr<Module> M1 = parseIR(Ctx, "@a = global i32 1\n");
 149   // clang-format off
 150   std::unique_ptr<Module> M2 = parseIR(
 151       Ctx, R"(
 152         @a = global i32 1
 153         @llvm.embedded.object = private constant [4 x i8] c"BC\C0\00", section ".llvm.lto", align 1, !exclude !0
 154         @llvm.compiler.used = appending global [1 x ptr] [ptr @llvm.embedded.object], section "llvm.metadata"
 155
 156         !llvm.embedded.objects = !{!1}
 157
 158         !0 = !{}
 159         !1 = !{ptr @llvm.embedded.object, !".llvm.lto"}
 160         )");
 161   // clang-format on
 162   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 163 }
 164
 165 TEST(StructuralHashTest, ComparisonInstructionPredicate) {
 166   LLVMContext Ctx;
 167   std::unique_ptr<Module> M1 = parseIR(Ctx, "define i1 @f(i64 %a, i64 %b) {\n"
 168                                             "  %1 = icmp eq i64 %a, %b\n"
 169                                             "  ret i1 %1\n"
 170                                             "}\n");
 171   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i1 @f(i64 %a, i64 %b) {\n"
 172                                             "  %1 = icmp ne i64 %a, %b\n"
 173                                             " ret i1 %1\n"
 174                                             "}\n");
 175   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 176   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 177 }
 178
 179 TEST(StructuralHashTest, IntrinsicInstruction) {
 180   LLVMContext Ctx;
 181   std::unique_ptr<Module> M1 =
 182       parseIR(Ctx, "define float @f(float %a) {\n"
 183                    "  %b = call float @llvm.sin.f32(float %a)\n"
 184                    "  ret float %b\n"
 185                    "}\n"
 186                    "declare float @llvm.sin.f32(float)\n");
 187   std::unique_ptr<Module> M2 =
 188       parseIR(Ctx, "define float @f(float %a) {\n"
 189                    "  %b = call float @llvm.cos.f32(float %a)\n"
 190                    "  ret float %b\n"
 191                    "}\n"
 192                    "declare float @llvm.cos.f32(float)\n");
 193   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 194   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 195 }
 196
 197 TEST(StructuralHashTest, CallInstruction) {
 198   LLVMContext Ctx;
 199   std::unique_ptr<Module> M1 = parseIR(Ctx, "define i64 @f(i64 %a) {\n"
 200                                             "  %b = call i64 @f1(i64 %a)\n"
 201                                             "  ret i64 %b\n"
 202                                             "}\n"
 203                                             "declare i64 @f1(i64)");
 204   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i64 @f(i64 %a) {\n"
 205                                             "  %b = call i64 @f2(i64 %a)\n"
 206                                             "  ret i64 %b\n"
 207                                             "}\n"
 208                                             "declare i64 @f2(i64)");
 209   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 210   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 211 }
 212
 213 TEST(StructuralHashTest, ConstantInteger) {
 214   LLVMContext Ctx;
 215   std::unique_ptr<Module> M1 = parseIR(Ctx, "define i64 @f1() {\n"
 216                                             "  ret i64 1\n"
 217                                             "}\n");
 218   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i64 @f2() {\n"
 219                                             "  ret i64 2\n"
 220                                             "}\n");
 221   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 222   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 223 }
 224
 225 TEST(StructuralHashTest, BigConstantInteger) {
 226   LLVMContext Ctx;
 227   std::unique_ptr<Module> M1 = parseIR(Ctx, "define i128 @f1() {\n"
 228                                             "  ret i128 18446744073709551616\n"
 229                                             "}\n");
 230   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i128 @f2() {\n"
 231                                             "  ret i128 18446744073709551617\n"
 232                                             "}\n");
 233   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 234   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 235 }
 236
 237 TEST(StructuralHashTest, ArgumentNumber) {
 238   LLVMContext Ctx;
 239   std::unique_ptr<Module> M1 = parseIR(Ctx, "define i64 @f1(i64 %a, i64 %b) {\n"
 240                                             "  ret i64 %a\n"
 241                                             "}\n");
 242   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i64 @f2(i64 %a, i64 %b) {\n"
 243                                             "  ret i64 %b\n"
 244                                             "}\n");
 245   EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));
 246   EXPECT_NE(StructuralHash(*M1, true), StructuralHash(*M2, true));
 247 }
 248
 249 TEST(StructuralHashTest, Differences) {
 250   LLVMContext Ctx;
 251   std::unique_ptr<Module> M1 = parseIR(Ctx, "define i64 @f(i64 %a) {\n"
 252                                             "  %c = add i64 %a, 1\n"
 253                                             "  %b = call i64 @f1(i64 %c)\n"
 254                                             "  ret i64 %b\n"
 255                                             "}\n"
 256                                             "declare i64 @f1(i64)");
 257   auto *F1 = M1->getFunction("f");
 258   std::unique_ptr<Module> M2 = parseIR(Ctx, "define i64 @g(i64 %a) {\n"
 259                                             "  %c = add i64 %a, 1\n"
 260                                             "  %b = call i64 @f2(i64 %c)\n"
 261                                             "  ret i64 %b\n"
 262                                             "}\n"
 263                                             "declare i64 @f2(i64)");
 264   auto *F2 = M2->getFunction("g");
 265
 266   // They are originally different when not ignoring any operand.
 267   EXPECT_NE(StructuralHash(*F1, true), StructuralHash(*F2, true));
 268   EXPECT_NE(StructuralHashWithDifferences(*F1, nullptr).FunctionHash,
 269             StructuralHashWithDifferences(*F2, nullptr).FunctionHash);
 270
 271   // When we ignore the call target f1 vs f2, they have the same hash.
 272   auto IgnoreOp = [&](const Instruction *I, unsigned OpndIdx) {
 273     return I->getOpcode() == Instruction::Call && OpndIdx == 1;
 274   };
 275   auto FuncHashInfo1 = StructuralHashWithDifferences(*F1, IgnoreOp);
 276   auto FuncHashInfo2 = StructuralHashWithDifferences(*F2, IgnoreOp);
 277   EXPECT_EQ(FuncHashInfo1.FunctionHash, FuncHashInfo2.FunctionHash);
 278
 279   // There are total 3 instructions.
 280   EXPECT_THAT(*FuncHashInfo1.IndexInstruction, SizeIs(3));
 281   EXPECT_THAT(*FuncHashInfo2.IndexInstruction, SizeIs(3));
 282
 283   // The only 1 operand (the call target) has been ignored.
 284   EXPECT_THAT(*FuncHashInfo1.IndexOperandHashMap, SizeIs(1u));
 285   EXPECT_THAT(*FuncHashInfo2.IndexOperandHashMap, SizeIs(1u));
 286
 287   // The index pair of instruction and operand (1, 1) is a key in the map.
 288   ASSERT_THAT(*FuncHashInfo1.IndexOperandHashMap, Contains(Key(Pair(1, 1))));
 289   ASSERT_THAT(*FuncHashInfo2.IndexOperandHashMap, Contains(Key(Pair(1, 1))));
 290
 291   // The indexed instruciton must be the call instruction as shown in the
 292   // IgnoreOp above.
 293   EXPECT_EQ(FuncHashInfo1.IndexInstruction->lookup(1)->getOpcode(),
 294             Instruction::Call);
 295   EXPECT_EQ(FuncHashInfo2.IndexInstruction->lookup(1)->getOpcode(),
 296             Instruction::Call);
 297
 298   // The ignored operand hashes (for f1 vs. f2) are different.
 299   EXPECT_NE(FuncHashInfo1.IndexOperandHashMap->lookup({1, 1}),
 300             FuncHashInfo2.IndexOperandHashMap->lookup({1, 1}));
 301 }
 302
 303 } // end anonymous namespace