304 lines · 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-exception6//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 18using namespace llvm;19 20namespace {21 22using testing::Contains;23using testing::Key;24using testing::Pair;25using testing::SizeIs;26 27std::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 35TEST(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 42TEST(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 56TEST(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 73TEST(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 82TEST(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 89TEST(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 96TEST(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 104TEST(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 118TEST(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 132TEST(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 146TEST(StructuralHashTest, IgnoredMetadata) {147 LLVMContext Ctx;148 std::unique_ptr<Module> M1 = parseIR(Ctx, "@a = global i32 1\n");149 // clang-format off150 std::unique_ptr<Module> M2 = parseIR(151 Ctx, R"(152 @a = global i32 1153 @llvm.embedded.object = private constant [4 x i8] c"BC\C0\00", section ".llvm.lto", align 1, !exclude !0154 @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 on162 EXPECT_EQ(StructuralHash(*M1), StructuralHash(*M2));163}164 165TEST(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 179TEST(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 197TEST(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 213TEST(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 225TEST(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 237TEST(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 249TEST(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 the292 // 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 namespace304