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 304