2849 lines · cpp
1//===- IRSimilarityIdentifierTest.cpp - IRSimilarityIdentifier unit tests -===//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// Tests for components for finding similarity such as the instruction mapper,10// suffix tree usage, and structural analysis.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/Analysis/IRSimilarityIdentifier.h"15#include "llvm/ADT/ScopeExit.h"16#include "llvm/AsmParser/Parser.h"17#include "llvm/IR/LLVMContext.h"18#include "llvm/IR/Module.h"19#include "llvm/Support/Allocator.h"20#include "llvm/Support/Compiler.h"21#include "llvm/Support/SourceMgr.h"22#include "gtest/gtest.h"23 24using namespace llvm;25using namespace IRSimilarity;26 27static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,28 StringRef ModuleStr) {29 SMDiagnostic Err;30 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);31 assert(M && "Bad LLVM IR?");32 return M;33}34 35void getVectors(Module &M, IRInstructionMapper &Mapper,36 std::vector<IRInstructionData *> &InstrList,37 std::vector<unsigned> &UnsignedVec) {38 for (Function &F : M)39 for (BasicBlock &BB : F)40 Mapper.convertToUnsignedVec(BB, InstrList, UnsignedVec);41}42 43void getSimilarities(44 Module &M,45 std::vector<std::vector<IRSimilarityCandidate>> &SimilarityCandidates) {46 // In order to keep the size of the tests from becoming too large, we do not47 // recognize similarity for branches unless explicitly needed.48 IRSimilarityIdentifier Identifier(/*EnableBranchMatching = */false);49 SimilarityCandidates = Identifier.findSimilarity(M);50}51 52// TODO: All these tests could probably become IR LIT tests like53// IROutliner/outlining-special-state.ll54 55// Checks that different opcodes are mapped to different values56TEST(IRInstructionMapper, OpcodeDifferentiation) {57 StringRef ModuleString = R"(58 define i32 @f(i32 %a, i32 %b) {59 bb0:60 %0 = add i32 %a, %b61 %1 = mul i32 %a, %b62 ret i32 063 })";64 LLVMContext Context;65 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);66 67 std::vector<IRInstructionData *> InstrList;68 std::vector<unsigned> UnsignedVec;69 70 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;71 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;72 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);73 getVectors(*M, Mapper, InstrList, UnsignedVec);74 75 // Check that the size of the unsigned vector and the instruction list are the76 // same as a safety check.77 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());78 79 // Make sure that the unsigned vector is the expected size.80 ASSERT_TRUE(UnsignedVec.size() == 3);81 82 // Check whether the instructions are not mapped to the same value.83 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);84}85 86// Checks that the same opcodes and types are mapped to the same values.87TEST(IRInstructionMapper, OpcodeTypeSimilarity) {88 StringRef ModuleString = R"(89 define i32 @f(i32 %a, i32 %b) {90 bb0:91 %0 = add i32 %a, %b92 %1 = add i32 %b, %a93 ret i32 094 })";95 LLVMContext Context;96 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);97 98 std::vector<IRInstructionData *> InstrList;99 std::vector<unsigned> UnsignedVec;100 101 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;102 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;103 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);104 getVectors(*M, Mapper, InstrList, UnsignedVec);105 106 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());107 ASSERT_TRUE(UnsignedVec.size() == 3);108 109 // Check whether the instructions are mapped to the same value.110 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);111}112 113// Checks that the same opcode and different types are mapped to different114// values.115TEST(IRInstructionMapper, TypeDifferentiation) {116 StringRef ModuleString = R"(117 define i32 @f(i32 %a, i32 %b, i64 %c, i64 %d) {118 bb0:119 %0 = add i32 %a, %b120 %1 = add i64 %c, %d121 ret i32 0122 })";123 LLVMContext Context;124 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);125 126 std::vector<IRInstructionData *> InstrList;127 std::vector<unsigned> UnsignedVec;128 129 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;130 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;131 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);132 getVectors(*M, Mapper, InstrList, UnsignedVec);133 134 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());135 ASSERT_TRUE(UnsignedVec.size() == 3);136 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);137}138 139// Checks that different predicates map to different values.140TEST(IRInstructionMapper, PredicateDifferentiation) {141 StringRef ModuleString = R"(142 define i32 @f(i32 %a, i32 %b) {143 bb0:144 %0 = icmp sge i32 %b, %a145 %1 = icmp slt i32 %a, %b146 ret i32 0147 })";148 LLVMContext Context;149 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);150 151 std::vector<IRInstructionData *> InstrList;152 std::vector<unsigned> UnsignedVec;153 154 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;155 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;156 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);157 getVectors(*M, Mapper, InstrList, UnsignedVec);158 159 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());160 ASSERT_TRUE(UnsignedVec.size() == 3);161 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);162}163 164// Checks that predicates where that can be considered the same when the165// operands are swapped, i.e. greater than to less than are mapped to the same166// unsigned integer.167TEST(IRInstructionMapper, PredicateIsomorphism) {168 StringRef ModuleString = R"(169 define i32 @f(i32 %a, i32 %b) {170 bb0:171 %0 = icmp sgt i32 %a, %b172 %1 = icmp slt i32 %b, %a173 ret i32 0174 })";175 LLVMContext Context;176 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);177 178 std::vector<IRInstructionData *> InstrList;179 std::vector<unsigned> UnsignedVec;180 181 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;182 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;183 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);184 getVectors(*M, Mapper, InstrList, UnsignedVec);185 186 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());187 ASSERT_TRUE(UnsignedVec.size() == 3);188 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);189}190 191// Checks that the same predicate maps to the same value.192TEST(IRInstructionMapper, PredicateSimilarity) {193 StringRef ModuleString = R"(194 define i32 @f(i32 %a, i32 %b) {195 bb0:196 %0 = icmp slt i32 %a, %b197 %1 = icmp slt i32 %b, %a198 ret i32 0199 })";200 LLVMContext Context;201 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);202 203 std::vector<IRInstructionData *> InstrList;204 std::vector<unsigned> UnsignedVec;205 206 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;207 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;208 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);209 getVectors(*M, Mapper, InstrList, UnsignedVec);210 211 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());212 ASSERT_TRUE(UnsignedVec.size() == 3);213 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);214}215 216// Checks that the same predicate maps to the same value for floating point217// CmpInsts.218TEST(IRInstructionMapper, FPPredicateSimilarity) {219 StringRef ModuleString = R"(220 define i32 @f(double %a, double %b) {221 bb0:222 %0 = fcmp olt double %a, %b223 %1 = fcmp olt double %b, %a224 ret i32 0225 })";226 LLVMContext Context;227 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);228 229 std::vector<IRInstructionData *> InstrList;230 std::vector<unsigned> UnsignedVec;231 232 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;233 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;234 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);235 getVectors(*M, Mapper, InstrList, UnsignedVec);236 237 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());238 ASSERT_TRUE(UnsignedVec.size() == 3);239 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);240}241 242// Checks that the different predicate maps to a different value for floating243// point CmpInsts.244TEST(IRInstructionMapper, FPPredicatDifference) {245 StringRef ModuleString = R"(246 define i32 @f(double %a, double %b) {247 bb0:248 %0 = fcmp olt double %a, %b249 %1 = fcmp oge double %b, %a250 ret i32 0251 })";252 LLVMContext Context;253 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);254 255 std::vector<IRInstructionData *> InstrList;256 std::vector<unsigned> UnsignedVec;257 258 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;259 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;260 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);261 getVectors(*M, Mapper, InstrList, UnsignedVec);262 263 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());264 ASSERT_TRUE(UnsignedVec.size() == 3);265 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);266}267 268// Checks that the zexts that have the same type parameters map to the same269// unsigned integer.270TEST(IRInstructionMapper, ZextTypeSimilarity) {271 StringRef ModuleString = R"(272 define i32 @f(i32 %a) {273 bb0:274 %0 = zext i32 %a to i64275 %1 = zext i32 %a to i64276 ret i32 0277 })";278 LLVMContext Context;279 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);280 281 std::vector<IRInstructionData *> InstrList;282 std::vector<unsigned> UnsignedVec;283 284 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;285 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;286 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);287 getVectors(*M, Mapper, InstrList, UnsignedVec);288 289 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());290 ASSERT_TRUE(UnsignedVec.size() == 3);291 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);292}293 294// Checks that the sexts that have the same type parameters map to the same295// unsigned integer.296TEST(IRInstructionMapper, SextTypeSimilarity) {297 StringRef ModuleString = R"(298 define i32 @f(i32 %a) {299 bb0:300 %0 = sext i32 %a to i64301 %1 = sext i32 %a to i64302 ret i32 0303 })";304 LLVMContext Context;305 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);306 307 std::vector<IRInstructionData *> InstrList;308 std::vector<unsigned> UnsignedVec;309 310 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;311 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;312 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);313 getVectors(*M, Mapper, InstrList, UnsignedVec);314 315 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());316 ASSERT_TRUE(UnsignedVec.size() == 3);317 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);318}319 320// Checks that the zexts that have the different type parameters map to the321// different unsigned integers.322TEST(IRInstructionMapper, ZextTypeDifference) {323 StringRef ModuleString = R"(324 define i32 @f(i32 %a, i8 %b) {325 bb0:326 %0 = zext i32 %a to i64327 %1 = zext i8 %b to i32328 ret i32 0329 })";330 LLVMContext Context;331 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);332 333 std::vector<IRInstructionData *> InstrList;334 std::vector<unsigned> UnsignedVec;335 336 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;337 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;338 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);339 getVectors(*M, Mapper, InstrList, UnsignedVec);340 341 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());342 ASSERT_TRUE(UnsignedVec.size() == 3);343 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);344}345 346// Checks that the sexts that have the different type parameters map to the347// different unsigned integers.348TEST(IRInstructionMapper, SextTypeDifference) {349 StringRef ModuleString = R"(350 define i32 @f(i32 %a, i8 %b) {351 bb0:352 %0 = sext i32 %a to i64353 %1 = sext i8 %b to i32354 ret i32 0355 })";356 LLVMContext Context;357 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);358 359 std::vector<IRInstructionData *> InstrList;360 std::vector<unsigned> UnsignedVec;361 362 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;363 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;364 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);365 getVectors(*M, Mapper, InstrList, UnsignedVec);366 367 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());368 ASSERT_TRUE(UnsignedVec.size() == 3);369 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);370}371 372// Checks that loads that have the same type are mapped to the same unsigned373// integer.374TEST(IRInstructionMapper, LoadSimilarType) {375 StringRef ModuleString = R"(376 define i32 @f(i32* %a, i32* %b) {377 bb0:378 %0 = load i32, i32* %a379 %1 = load i32, i32* %b380 ret i32 0381 })";382 LLVMContext Context;383 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);384 385 std::vector<IRInstructionData *> InstrList;386 std::vector<unsigned> UnsignedVec;387 388 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;389 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;390 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);391 getVectors(*M, Mapper, InstrList, UnsignedVec);392 393 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());394 ASSERT_TRUE(UnsignedVec.size() == 3);395 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);396}397 398// Checks that loads that have the different types are mapped to399// different unsigned integers.400TEST(IRInstructionMapper, LoadDifferentType) {401 StringRef ModuleString = R"(402 define i32 @f(i32* %a, i64* %b) {403 bb0:404 %0 = load i32, i32* %a405 %1 = load i64, i64* %b406 ret i32 0407 })";408 LLVMContext Context;409 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);410 411 std::vector<IRInstructionData *> InstrList;412 std::vector<unsigned> UnsignedVec;413 414 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;415 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;416 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);417 getVectors(*M, Mapper, InstrList, UnsignedVec);418 419 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());420 ASSERT_TRUE(UnsignedVec.size() == 3);421 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);422}423 424// Checks that loads that have the different aligns are mapped to different425// unsigned integers.426TEST(IRInstructionMapper, LoadDifferentAlign) {427 StringRef ModuleString = R"(428 define i32 @f(i32* %a, i32* %b) {429 bb0:430 %0 = load i32, i32* %a, align 4431 %1 = load i32, i32* %b, align 8432 ret i32 0433 })";434 LLVMContext Context;435 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);436 437 std::vector<IRInstructionData *> InstrList;438 std::vector<unsigned> UnsignedVec;439 440 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;441 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;442 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);443 getVectors(*M, Mapper, InstrList, UnsignedVec);444 445 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());446 ASSERT_TRUE(UnsignedVec.size() == 3);447 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);448}449 450// Checks that loads that have the different volatile settings are mapped to451// different unsigned integers.452TEST(IRInstructionMapper, LoadDifferentVolatile) {453 StringRef ModuleString = R"(454 define i32 @f(i32* %a, i32* %b) {455 bb0:456 %0 = load volatile i32, i32* %a457 %1 = load i32, i32* %b458 ret i32 0459 })";460 LLVMContext Context;461 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);462 463 std::vector<IRInstructionData *> InstrList;464 std::vector<unsigned> UnsignedVec;465 466 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;467 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;468 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);469 getVectors(*M, Mapper, InstrList, UnsignedVec);470 471 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());472 ASSERT_TRUE(UnsignedVec.size() == 3);473 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);474}475 476// Checks that loads that have the same volatile settings are mapped to477// different unsigned integers.478TEST(IRInstructionMapper, LoadSameVolatile) {479 StringRef ModuleString = R"(480 define i32 @f(i32* %a, i32* %b) {481 bb0:482 %0 = load volatile i32, i32* %a483 %1 = load volatile i32, i32* %b484 ret i32 0485 })";486 LLVMContext Context;487 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);488 489 std::vector<IRInstructionData *> InstrList;490 std::vector<unsigned> UnsignedVec;491 492 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;493 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;494 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);495 getVectors(*M, Mapper, InstrList, UnsignedVec);496 497 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());498 ASSERT_TRUE(UnsignedVec.size() == 3);499 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);500}501 502// Checks that loads that have the different atomicity settings are mapped to503// different unsigned integers.504TEST(IRInstructionMapper, LoadDifferentAtomic) {505 StringRef ModuleString = R"(506 define i32 @f(i32* %a, i32* %b) {507 bb0:508 %0 = load atomic i32, i32* %a unordered, align 4509 %1 = load atomic i32, i32* %b monotonic, align 4510 ret i32 0511 })";512 LLVMContext Context;513 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);514 515 std::vector<IRInstructionData *> InstrList;516 std::vector<unsigned> UnsignedVec;517 518 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;519 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;520 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);521 getVectors(*M, Mapper, InstrList, UnsignedVec);522 523 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());524 ASSERT_TRUE(UnsignedVec.size() == 3);525 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);526}527 528// Checks that loads that have the same atomicity settings are mapped to529// different unsigned integers.530TEST(IRInstructionMapper, LoadSameAtomic) {531 StringRef ModuleString = R"(532 define i32 @f(i32* %a, i32* %b) {533 bb0:534 %0 = load atomic i32, i32* %a unordered, align 4535 %1 = load atomic i32, i32* %b unordered, align 4536 ret i32 0537 })";538 LLVMContext Context;539 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);540 541 std::vector<IRInstructionData *> InstrList;542 std::vector<unsigned> UnsignedVec;543 544 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;545 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;546 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);547 getVectors(*M, Mapper, InstrList, UnsignedVec);548 549 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());550 ASSERT_TRUE(UnsignedVec.size() == 3);551 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);552}553 554// Checks that stores that have the same type are mapped to the same unsigned555// integer.556TEST(IRInstructionMapper, StoreSimilarType) {557 StringRef ModuleString = R"(558 define i32 @f(i32* %a, i32* %b) {559 bb0:560 store i32 1, i32* %a561 store i32 2, i32* %a562 ret i32 0563 })";564 LLVMContext Context;565 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);566 567 std::vector<IRInstructionData *> InstrList;568 std::vector<unsigned> UnsignedVec;569 570 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;571 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;572 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);573 getVectors(*M, Mapper, InstrList, UnsignedVec);574 575 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());576 ASSERT_TRUE(UnsignedVec.size() == 3);577 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);578}579 580// Checks that stores that have the different types are mapped to581// different unsigned integers.582TEST(IRInstructionMapper, StoreDifferentType) {583 StringRef ModuleString = R"(584 define i32 @f(i32* %a, i64* %b) {585 bb0:586 store i32 1, i32* %a587 store i64 1, i64* %b588 ret i32 0589 })";590 LLVMContext Context;591 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);592 593 std::vector<IRInstructionData *> InstrList;594 std::vector<unsigned> UnsignedVec;595 596 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;597 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;598 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);599 getVectors(*M, Mapper, InstrList, UnsignedVec);600 601 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());602 ASSERT_TRUE(UnsignedVec.size() == 3);603 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);604}605 606// Checks that stores that have the different aligns are mapped to different607// unsigned integers.608TEST(IRInstructionMapper, StoreDifferentAlign) {609 StringRef ModuleString = R"(610 define i32 @f(i32* %a, i32* %b) {611 bb0:612 store i32 1, i32* %a, align 4613 store i32 1, i32* %b, align 8614 ret i32 0615 })";616 LLVMContext Context;617 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);618 619 std::vector<IRInstructionData *> InstrList;620 std::vector<unsigned> UnsignedVec;621 622 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;623 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;624 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);625 getVectors(*M, Mapper, InstrList, UnsignedVec);626 627 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());628 ASSERT_TRUE(UnsignedVec.size() == 3);629 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);630}631 632// Checks that stores that have the different volatile settings are mapped to633// different unsigned integers.634TEST(IRInstructionMapper, StoreDifferentVolatile) {635 StringRef ModuleString = R"(636 define i32 @f(i32* %a, i32* %b) {637 bb0:638 store volatile i32 1, i32* %a639 store i32 1, i32* %b640 ret i32 0641 })";642 LLVMContext Context;643 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);644 645 std::vector<IRInstructionData *> InstrList;646 std::vector<unsigned> UnsignedVec;647 648 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;649 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;650 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);651 getVectors(*M, Mapper, InstrList, UnsignedVec);652 653 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());654 ASSERT_TRUE(UnsignedVec.size() == 3);655 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);656}657 658// Checks that stores that have the same volatile settings are mapped to659// different unsigned integers.660TEST(IRInstructionMapper, StoreSameVolatile) {661 StringRef ModuleString = R"(662 define i32 @f(i32* %a, i32* %b) {663 bb0:664 store volatile i32 1, i32* %a665 store volatile i32 1, i32* %b666 ret i32 0667 })";668 LLVMContext Context;669 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);670 671 std::vector<IRInstructionData *> InstrList;672 std::vector<unsigned> UnsignedVec;673 674 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;675 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;676 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);677 getVectors(*M, Mapper, InstrList, UnsignedVec);678 679 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());680 ASSERT_TRUE(UnsignedVec.size() == 3);681 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);682}683 684// Checks that loads that have the same atomicity settings are mapped to685// different unsigned integers.686TEST(IRInstructionMapper, StoreSameAtomic) {687 StringRef ModuleString = R"(688 define i32 @f(i32* %a, i32* %b) {689 bb0:690 store atomic i32 1, i32* %a unordered, align 4691 store atomic i32 1, i32* %b unordered, align 4692 ret i32 0693 })";694 LLVMContext Context;695 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);696 697 std::vector<IRInstructionData *> InstrList;698 std::vector<unsigned> UnsignedVec;699 700 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;701 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;702 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);703 getVectors(*M, Mapper, InstrList, UnsignedVec);704 705 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());706 ASSERT_TRUE(UnsignedVec.size() == 3);707 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);708}709 710// Checks that loads that have the different atomicity settings are mapped to711// different unsigned integers.712TEST(IRInstructionMapper, StoreDifferentAtomic) {713 StringRef ModuleString = R"(714 define i32 @f(i32* %a, i32* %b) {715 bb0:716 store atomic i32 1, i32* %a unordered, align 4717 store atomic i32 1, i32* %b monotonic, align 4718 ret i32 0719 })";720 LLVMContext Context;721 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);722 723 std::vector<IRInstructionData *> InstrList;724 std::vector<unsigned> UnsignedVec;725 726 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;727 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;728 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);729 getVectors(*M, Mapper, InstrList, UnsignedVec);730 731 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());732 ASSERT_TRUE(UnsignedVec.size() == 3);733 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);734}735 736// Checks that the branch is mapped to legal when the option is set.737TEST(IRInstructionMapper, BranchLegal) {738 StringRef ModuleString = R"(739 define i32 @f(i32 %a, i32 %b) {740 bb0:741 %0 = icmp slt i32 %a, %b742 br i1 %0, label %bb0, label %bb1743 bb1:744 ret i32 0745 })";746 LLVMContext Context;747 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);748 749 std::vector<IRInstructionData *> InstrList;750 std::vector<unsigned> UnsignedVec;751 752 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;753 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;754 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);755 Mapper.InstClassifier.EnableBranches = true;756 Mapper.initializeForBBs(*M);757 getVectors(*M, Mapper, InstrList, UnsignedVec);758 759 ASSERT_EQ(InstrList.size(), UnsignedVec.size());760 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));761 ASSERT_TRUE(UnsignedVec[1] > UnsignedVec[0]);762 ASSERT_TRUE(UnsignedVec[1] < UnsignedVec[2]);763}764 765// Checks that a PHINode is mapped to be legal.766TEST(IRInstructionMapper, PhiLegal) {767 StringRef ModuleString = R"(768 define i32 @f(i32 %a, i32 %b) {769 bb0:770 %0 = phi i1 [ 0, %bb0 ], [ %0, %bb1 ]771 %1 = add i32 %a, %b772 ret i32 0773 bb1:774 ret i32 1775 })";776 LLVMContext Context;777 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);778 779 std::vector<IRInstructionData *> InstrList;780 std::vector<unsigned> UnsignedVec;781 782 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;783 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;784 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);785 Mapper.InstClassifier.EnableBranches = true;786 Mapper.initializeForBBs(*M);787 getVectors(*M, Mapper, InstrList, UnsignedVec);788 789 ASSERT_EQ(InstrList.size(), UnsignedVec.size());790 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));791}792 793// Checks that a PHINode is mapped to be legal.794TEST(IRInstructionMapper, PhiIllegal) {795 StringRef ModuleString = R"(796 define i32 @f(i32 %a, i32 %b) {797 bb0:798 %0 = phi i1 [ 0, %bb0 ], [ %0, %bb1 ]799 %1 = add i32 %a, %b800 ret i32 0801 bb1:802 ret i32 1803 })";804 LLVMContext Context;805 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);806 807 std::vector<IRInstructionData *> InstrList;808 std::vector<unsigned> UnsignedVec;809 810 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;811 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;812 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);813 Mapper.initializeForBBs(*M);814 getVectors(*M, Mapper, InstrList, UnsignedVec);815 816 ASSERT_EQ(InstrList.size(), UnsignedVec.size());817 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));818 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);819}820 821// In most cases, the illegal instructions we are collecting don't require any822// sort of setup. In these cases, we can just only have illegal instructions,823// and the mapper will create 0 length vectors, and we can check that.824 825// In cases where we have legal instructions needed to set up the illegal826// instruction, to check illegal instructions are assigned unsigned integers827// from the maximum value decreasing to 0, it will be greater than a legal828// instruction that comes after. So to check that we have an illegal829// instruction, we place a legal instruction after an illegal instruction, and830// check that the illegal unsigned integer is greater than the unsigned integer831// of the legal instruction.832 833// Checks that an alloca instruction is mapped to be illegal.834TEST(IRInstructionMapper, AllocaIllegal) {835 StringRef ModuleString = R"(836 define i32 @f(i32 %a, i32 %b) {837 bb0:838 %0 = alloca i32839 ret i32 0840 })";841 LLVMContext Context;842 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);843 844 std::vector<IRInstructionData *> InstrList;845 std::vector<unsigned> UnsignedVec;846 847 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;848 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;849 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);850 getVectors(*M, Mapper, InstrList, UnsignedVec);851 852 ASSERT_EQ(InstrList.size(), UnsignedVec.size());853 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));854 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);855}856 857// Checks that an getelementptr instruction is mapped to be legal. And that858// the operands in getelementpointer instructions are the exact same after the859// first element operand, which only requires the same type.860TEST(IRInstructionMapper, GetElementPtrSameEndOperands) {861 StringRef ModuleString = R"(862 %struct.RT = type { i8, [10 x [20 x i32]], i8 }863 %struct.ST = type { i32, double, %struct.RT }864 define i32 @f(%struct.ST* %s, i64 %a, i64 %b) {865 bb0:866 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0867 %1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %b, i32 0868 ret i32 0869 })";870 LLVMContext Context;871 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);872 873 std::vector<IRInstructionData *> InstrList;874 std::vector<unsigned> UnsignedVec;875 876 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;877 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;878 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);879 getVectors(*M, Mapper, InstrList, UnsignedVec);880 881 ASSERT_EQ(InstrList.size(), UnsignedVec.size());882 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));883 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);884}885 886// Check that when the operands in getelementpointer instructions are not the887// exact same after the first element operand, the instructions are mapped to888// different values.889TEST(IRInstructionMapper, GetElementPtrDifferentEndOperands) {890 StringRef ModuleString = R"(891 %struct.RT = type { i8, [10 x [20 x i32]], i8 }892 %struct.ST = type { i32, double, %struct.RT }893 define i32 @f(%struct.ST* %s, i64 %a, i64 %b) {894 bb0:895 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0896 %1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %b, i32 2897 ret i32 0898 })";899 LLVMContext Context;900 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);901 902 std::vector<IRInstructionData *> InstrList;903 std::vector<unsigned> UnsignedVec;904 905 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;906 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;907 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);908 getVectors(*M, Mapper, InstrList, UnsignedVec);909 910 ASSERT_EQ(InstrList.size(), UnsignedVec.size());911 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));912 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);913}914 915// Check that when the operands in getelementpointer instructions are not the916// same initial base type, each instruction is mapped to a different value.917TEST(IRInstructionMapper, GetElementPtrDifferentBaseType) {918 StringRef ModuleString = R"(919 %struct.RT = type { i8, [10 x [20 x i32]], i8 }920 %struct.ST = type { i32, double, %struct.RT }921 define i32 @f(%struct.ST* %s, %struct.RT* %r, i64 %a, i64 %b) {922 bb0:923 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a924 %1 = getelementptr inbounds %struct.RT, %struct.RT* %r, i64 %b925 ret i32 0926 })";927 LLVMContext Context;928 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);929 930 std::vector<IRInstructionData *> InstrList;931 std::vector<unsigned> UnsignedVec;932 933 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;934 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;935 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);936 getVectors(*M, Mapper, InstrList, UnsignedVec);937 938 ASSERT_EQ(InstrList.size(), UnsignedVec.size());939 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));940 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);941}942 943// Check that when the operands in getelementpointer instructions do not have944// the same inbounds modifier, they are not counted as the same.945TEST(IRInstructionMapper, GetElementPtrDifferentInBounds) {946 StringRef ModuleString = R"(947 %struct.RT = type { i8, [10 x [20 x i32]], i8 }948 %struct.ST = type { i32, double, %struct.RT }949 define i32 @f(%struct.ST* %s, %struct.RT* %r, i64 %a, i64 %b) {950 bb0:951 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0952 %1 = getelementptr %struct.ST, %struct.ST* %s, i64 %b, i32 0953 ret i32 0954 })";955 LLVMContext Context;956 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);957 958 std::vector<IRInstructionData *> InstrList;959 std::vector<unsigned> UnsignedVec;960 961 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;962 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;963 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);964 getVectors(*M, Mapper, InstrList, UnsignedVec);965 966 ASSERT_EQ(InstrList.size(), UnsignedVec.size());967 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));968 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);969}970 971// Checks that indirect call instructions are mapped to be illegal when it is972// specified to disallow them.973TEST(IRInstructionMapper, CallsIllegalIndirect) {974 StringRef ModuleString = R"(975 define i32 @f(void()* %func) {976 bb0:977 call void %func()978 ret i32 0979 })";980 LLVMContext Context;981 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);982 983 std::vector<IRInstructionData *> InstrList;984 std::vector<unsigned> UnsignedVec;985 986 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;987 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;988 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);989 Mapper.InstClassifier.EnableIndirectCalls = false;990 getVectors(*M, Mapper, InstrList, UnsignedVec);991 992 ASSERT_EQ(InstrList.size(), UnsignedVec.size());993 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));994 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);995}996 997// Checks that indirect call instructions are mapped to be legal when it is not998// specified to disallow them.999TEST(IRInstructionMapper, CallsLegalIndirect) {1000 StringRef ModuleString = R"(1001 define i32 @f(void()* %func) {1002 bb0:1003 call void %func()1004 call void %func()1005 ret i32 01006 })";1007 LLVMContext Context;1008 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1009 1010 std::vector<IRInstructionData *> InstrList;1011 std::vector<unsigned> UnsignedVec;1012 1013 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1014 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1015 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1016 Mapper.InstClassifier.EnableIndirectCalls = true;1017 getVectors(*M, Mapper, InstrList, UnsignedVec);1018 1019 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1020 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1021}1022 1023// Checks that a call instruction is mapped to be legal. Here we check that1024// a call with the same name, and same types are mapped to the same1025// value.1026TEST(IRInstructionMapper, CallsSameTypeSameName) {1027 StringRef ModuleString = R"(1028 declare i32 @f1(i32, i32)1029 define i32 @f(i32 %a, i32 %b) {1030 bb0:1031 %0 = call i32 @f1(i32 %a, i32 %b)1032 %1 = call i32 @f1(i32 %a, i32 %b)1033 ret i32 01034 })";1035 LLVMContext Context;1036 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1037 1038 std::vector<IRInstructionData *> InstrList;1039 std::vector<unsigned> UnsignedVec;1040 1041 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1042 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1043 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1044 getVectors(*M, Mapper, InstrList, UnsignedVec);1045 1046 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1047 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1048 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);1049}1050 1051// Here we check that a calls with different names, but the same arguments types1052// are mapped to different value when specified that the name must match.1053TEST(IRInstructionMapper, CallsSameArgTypeDifferentNameDisallowed) {1054 StringRef ModuleString = R"(1055 declare i32 @f1(i32, i32)1056 declare i32 @f2(i32, i32)1057 define i32 @f(i32 %a, i32 %b) {1058 bb0:1059 %0 = call i32 @f1(i32 %a, i32 %b)1060 %1 = call i32 @f2(i32 %a, i32 %b)1061 ret i32 01062 })";1063 LLVMContext Context;1064 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1065 1066 std::vector<IRInstructionData *> InstrList;1067 std::vector<unsigned> UnsignedVec;1068 1069 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1070 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1071 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1072 Mapper.EnableMatchCallsByName = true;1073 getVectors(*M, Mapper, InstrList, UnsignedVec);1074 1075 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1076 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1077 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);1078}1079 1080// Here we check that a calls with different names, but the same arguments types1081// are mapped to the same value when it is not specifed that they must match.1082TEST(IRInstructionMapper, CallsSameArgTypeDifferentName) {1083 StringRef ModuleString = R"(1084 declare i32 @f1(i32, i32)1085 declare i32 @f2(i32, i32)1086 define i32 @f(i32 %a, i32 %b) {1087 bb0:1088 %0 = call i32 @f1(i32 %a, i32 %b)1089 %1 = call i32 @f2(i32 %a, i32 %b)1090 ret i32 01091 })";1092 LLVMContext Context;1093 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1094 1095 std::vector<IRInstructionData *> InstrList;1096 std::vector<unsigned> UnsignedVec;1097 1098 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1099 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1100 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1101 Mapper.EnableMatchCallsByName = false;1102 getVectors(*M, Mapper, InstrList, UnsignedVec);1103 1104 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1105 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1106 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);1107}1108 1109// Here we check that a calls with different names, and different arguments1110// types are mapped to different value.1111TEST(IRInstructionMapper, CallsDifferentArgTypeDifferentName) {1112 StringRef ModuleString = R"(1113 declare i32 @f1(i32, i32)1114 declare i32 @f2(i32)1115 define i32 @f(i32 %a, i32 %b) {1116 bb0:1117 %0 = call i32 @f1(i32 %a, i32 %b)1118 %1 = call i32 @f2(i32 %a)1119 ret i32 01120 })";1121 LLVMContext Context;1122 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1123 1124 std::vector<IRInstructionData *> InstrList;1125 std::vector<unsigned> UnsignedVec;1126 1127 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1128 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1129 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1130 getVectors(*M, Mapper, InstrList, UnsignedVec);1131 1132 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1133 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1134 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);1135}1136 1137// Here we check that calls with different names, and different return1138// types are mapped to different value.1139TEST(IRInstructionMapper, CallsDifferentReturnTypeDifferentName) {1140 StringRef ModuleString = R"(1141 declare i64 @f1(i32, i32)1142 declare i32 @f2(i32, i32)1143 define i32 @f(i32 %a, i32 %b) {1144 bb0:1145 %0 = call i64 @f1(i32 %a, i32 %b)1146 %1 = call i32 @f2(i32 %a, i32 %b)1147 ret i32 01148 })";1149 LLVMContext Context;1150 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1151 1152 std::vector<IRInstructionData *> InstrList;1153 std::vector<unsigned> UnsignedVec;1154 1155 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1156 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1157 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1158 getVectors(*M, Mapper, InstrList, UnsignedVec);1159 1160 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1161 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1162 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);1163}1164 1165// Here we check that calls with the same name, types, and parameters map to the1166// same unsigned integer.1167TEST(IRInstructionMapper, CallsSameParameters) {1168 StringRef ModuleString = R"(1169 declare i32 @f1(i32, i32)1170 define i32 @f(i32 %a, i32 %b) {1171 bb0:1172 %0 = tail call fastcc i32 @f1(i32 %a, i32 %b)1173 %1 = tail call fastcc i32 @f1(i32 %a, i32 %b)1174 ret i32 01175 })";1176 LLVMContext Context;1177 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1178 1179 std::vector<IRInstructionData *> InstrList;1180 std::vector<unsigned> UnsignedVec;1181 1182 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1183 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1184 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1185 getVectors(*M, Mapper, InstrList, UnsignedVec);1186 1187 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1188 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1189 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);1190}1191 1192// Here we check that calls with different tail call settings are mapped to1193// different values.1194TEST(IRInstructionMapper, CallsDifferentTails) {1195 StringRef ModuleString = R"(1196 declare i32 @f1(i32, i32)1197 define i32 @f(i32 %a, i32 %b) {1198 bb0:1199 %0 = tail call i32 @f1(i32 %a, i32 %b)1200 %1 = call i32 @f1(i32 %a, i32 %b)1201 ret i32 01202 })";1203 LLVMContext Context;1204 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1205 1206 std::vector<IRInstructionData *> InstrList;1207 std::vector<unsigned> UnsignedVec;1208 1209 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1210 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1211 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1212 getVectors(*M, Mapper, InstrList, UnsignedVec);1213 1214 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1215 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1216 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);1217}1218 1219// Here we check that calls with different calling convention settings are1220// mapped to different values.1221TEST(IRInstructionMapper, CallsDifferentCallingConventions) {1222 StringRef ModuleString = R"(1223 declare i32 @f1(i32, i32)1224 define i32 @f(i32 %a, i32 %b) {1225 bb0:1226 %0 = call fastcc i32 @f1(i32 %a, i32 %b)1227 %1 = call i32 @f1(i32 %a, i32 %b)1228 ret i32 01229 })";1230 LLVMContext Context;1231 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1232 1233 std::vector<IRInstructionData *> InstrList;1234 std::vector<unsigned> UnsignedVec;1235 1236 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1237 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1238 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1239 getVectors(*M, Mapper, InstrList, UnsignedVec);1240 1241 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1242 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1243 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);1244}1245 1246// Checks that an invoke instruction is mapped to be illegal. Invoke1247// instructions are considered to be illegal because of the change in the1248// control flow that is currently not recognized.1249TEST(IRInstructionMapper, InvokeIllegal) {1250 StringRef ModuleString = R"(1251 define i32 @f(i8 *%gep1, i32 %b) {1252 then: 1253 invoke i32 undef(i8* undef)1254 to label %invoke unwind label %lpad1255 1256 invoke:1257 unreachable1258 1259 lpad:1260 landingpad { i8*, i32 }1261 catch i8* null1262 unreachable1263 })";1264 LLVMContext Context;1265 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1266 1267 std::vector<IRInstructionData *> InstrList;1268 std::vector<unsigned> UnsignedVec;1269 1270 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1271 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1272 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1273 getVectors(*M, Mapper, InstrList, UnsignedVec);1274 1275 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1276 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1277 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1278}1279 1280// Checks that an callbr instructions are considered to be illegal. Callbr1281// instructions are considered to be illegal because of the change in the1282// control flow that is currently not recognized.1283TEST(IRInstructionMapper, CallBrInstIllegal) {1284 StringRef ModuleString = R"(1285 define void @test() {1286 fail:1287 ret void1288 }1289 1290 define i32 @f(i32 %a, i32 %b) {1291 bb0:1292 callbr void asm "xorl $0, $0; jmp ${1:l}", "r,X,~{dirflag},~{fpsr},~{flags}"(i32 %a, i8* blockaddress(@test, %fail)) to label %normal [label %fail]1293 fail:1294 ret i32 01295 normal:1296 ret i32 01297 })";1298 LLVMContext Context;1299 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1300 1301 std::vector<IRInstructionData *> InstrList;1302 std::vector<unsigned> UnsignedVec;1303 1304 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1305 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1306 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1307 getVectors(*M, Mapper, InstrList, UnsignedVec);1308 1309 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1310 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1311 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1312}1313 1314// Checks that an debuginfo records are mapped to be invisible. Since they1315// do not semantically change the program, they can be recognized as similar.1316TEST(IRInstructionMapper, DebugInfoInvisible) {1317 StringRef ModuleString = R"(1318 define i32 @f(i32 %a, i32 %b) {1319 then:1320 %0 = add i32 %a, %b1321 #dbg_value(i32 0, !0, !0, !0)1322 %1 = add i32 %a, %b1323 ret i32 01324 }1325 1326 !0 = distinct !{!"test\00", i32 10})";1327 LLVMContext Context;1328 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1329 1330 std::vector<IRInstructionData *> InstrList;1331 std::vector<unsigned> UnsignedVec;1332 1333 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1334 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1335 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1336 getVectors(*M, Mapper, InstrList, UnsignedVec);1337 1338 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1339 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));1340}1341 1342// The following are all exception handling intrinsics. We do not currently1343// handle these instruction because they are very context dependent.1344 1345// Checks that an eh.typeid.for intrinsic is mapped to be illegal.1346TEST(IRInstructionMapper, ExceptionHandlingTypeIdIllegal) {1347 StringRef ModuleString = R"(1348 @_ZTIi = external constant i8*1349 define i32 @f() {1350 then:1351 %0 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))1352 ret i32 01353 }1354 1355 declare i32 @llvm.eh.typeid.for(i8*))";1356 LLVMContext Context;1357 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1358 1359 std::vector<IRInstructionData *> InstrList;1360 std::vector<unsigned> UnsignedVec;1361 1362 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1363 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1364 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1365 getVectors(*M, Mapper, InstrList, UnsignedVec);1366 1367 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1368 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1369 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1370}1371 1372// Checks that an eh.exceptioncode intrinsic is mapped to be illegal.1373TEST(IRInstructionMapper, ExceptionHandlingExceptionCodeIllegal) {1374 StringRef ModuleString = R"(1375 define i32 @f(i32 %a, i32 %b) {1376 entry:1377 %0 = catchswitch within none [label %__except] unwind to caller1378 1379 __except:1380 %1 = catchpad within %0 [i8* null]1381 catchret from %1 to label %__except1382 1383 then:1384 %2 = call i32 @llvm.eh.exceptioncode(token %1)1385 ret i32 01386 }1387 1388 declare i32 @llvm.eh.exceptioncode(token))";1389 LLVMContext Context;1390 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1391 1392 std::vector<IRInstructionData *> InstrList;1393 std::vector<unsigned> UnsignedVec;1394 1395 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1396 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1397 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1398 getVectors(*M, Mapper, InstrList, UnsignedVec);1399 1400 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1401 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1402 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1403}1404 1405// Checks that an eh.unwind intrinsic is mapped to be illegal.1406TEST(IRInstructionMapper, ExceptionHandlingUnwindIllegal) {1407 StringRef ModuleString = R"(1408 define i32 @f(i32 %a, i32 %b) {1409 entry:1410 call void @llvm.eh.unwind.init()1411 ret i32 01412 }1413 1414 declare void @llvm.eh.unwind.init())";1415 LLVMContext Context;1416 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1417 1418 std::vector<IRInstructionData *> InstrList;1419 std::vector<unsigned> UnsignedVec;1420 1421 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1422 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1423 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1424 getVectors(*M, Mapper, InstrList, UnsignedVec);1425 1426 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1427 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1428 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1429}1430 1431// Checks that an eh.exceptionpointer intrinsic is mapped to be illegal.1432TEST(IRInstructionMapper, ExceptionHandlingExceptionPointerIllegal) {1433 StringRef ModuleString = R"(1434 define i32 @f(i32 %a, i32 %b) {1435 entry:1436 %0 = call i8* @llvm.eh.exceptionpointer.p0i8(i32 0)1437 ret i32 01438 }1439 1440 declare i8* @llvm.eh.exceptionpointer.p0i8(i32))";1441 LLVMContext Context;1442 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1443 1444 std::vector<IRInstructionData *> InstrList;1445 std::vector<unsigned> UnsignedVec;1446 1447 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1448 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1449 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1450 getVectors(*M, Mapper, InstrList, UnsignedVec);1451 1452 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1453 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1454 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1455}1456 1457// Checks that a catchpad instruction is mapped to an illegal value.1458TEST(IRInstructionMapper, CatchpadIllegal) {1459 StringRef ModuleString = R"(1460 declare void @llvm.donothing() nounwind readnone1461 1462 define void @function() personality i8 3 {1463 entry:1464 invoke void @llvm.donothing() to label %normal unwind label %exception1465 exception:1466 %cs1 = catchswitch within none [label %catchpad1] unwind to caller1467 catchpad1:1468 catchpad within %cs1 []1469 br label %normal1470 normal:1471 ret void1472 })";1473 LLVMContext Context;1474 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1475 1476 std::vector<IRInstructionData *> InstrList;1477 std::vector<unsigned> UnsignedVec;1478 1479 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1480 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1481 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1482 getVectors(*M, Mapper, InstrList, UnsignedVec);1483 1484 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1485 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1486 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1487}1488 1489// Checks that a cleanuppad instruction is mapped to an illegal value.1490TEST(IRInstructionMapper, CleanuppadIllegal) {1491 StringRef ModuleString = R"(1492 declare void @llvm.donothing() nounwind readnone1493 1494 define void @function() personality i8 3 {1495 entry:1496 invoke void @llvm.donothing() to label %normal unwind label %exception1497 exception:1498 %cs1 = catchswitch within none [label %catchpad1] unwind to caller1499 catchpad1:1500 %clean = cleanuppad within none []1501 br label %normal1502 normal:1503 ret void1504 })";1505 LLVMContext Context;1506 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1507 1508 std::vector<IRInstructionData *> InstrList;1509 std::vector<unsigned> UnsignedVec;1510 1511 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1512 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1513 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1514 getVectors(*M, Mapper, InstrList, UnsignedVec);1515 1516 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1517 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));1518 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);1519}1520 1521// The following three instructions are memory transfer and setting based, which1522// are considered illegal since is extra checking needed to handle the address1523// space checking.1524 1525// Checks that a memset instruction is mapped to an illegal value when1526// specified.1527TEST(IRInstructionMapper, MemSetIllegal) {1528 StringRef ModuleString = R"(1529 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)1530 1531 define i64 @function(i64 %x, i64 %z, i64 %n) {1532 entry:1533 %pool = alloca [59 x i64], align 41534 %tmp = bitcast [59 x i64]* %pool to i8*1535 call void @llvm.memset.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)1536 %cmp3 = icmp eq i64 %n, 01537 %a = add i64 %x, %z1538 %c = add i64 %x, %z1539 ret i64 01540 })";1541 LLVMContext Context;1542 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1543 1544 std::vector<IRInstructionData *> InstrList;1545 std::vector<unsigned> UnsignedVec;1546 1547 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1548 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1549 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1550 Mapper.InstClassifier.EnableIntrinsics = false;1551 getVectors(*M, Mapper, InstrList, UnsignedVec);1552 1553 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1554 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));1555 ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[0]);1556}1557 1558// Checks that a memcpy instruction is mapped to an illegal value when1559// specified.1560TEST(IRInstructionMapper, MemCpyIllegal) {1561 StringRef ModuleString = R"(1562 declare void @llvm.memcpy.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)1563 1564 define i64 @function(i64 %x, i64 %z, i64 %n) {1565 entry:1566 %pool = alloca [59 x i64], align 41567 %tmp = bitcast [59 x i64]* %pool to i8*1568 call void @llvm.memcpy.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)1569 %cmp3 = icmp eq i64 %n, 01570 %a = add i64 %x, %z1571 %c = add i64 %x, %z1572 ret i64 01573 })";1574 LLVMContext Context;1575 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1576 1577 std::vector<IRInstructionData *> InstrList;1578 std::vector<unsigned> UnsignedVec;1579 1580 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1581 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1582 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1583 Mapper.InstClassifier.EnableIntrinsics = false;1584 getVectors(*M, Mapper, InstrList, UnsignedVec);1585 1586 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1587 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));1588 ASSERT_GT(UnsignedVec[2], UnsignedVec[3]);1589 ASSERT_LT(UnsignedVec[2], UnsignedVec[0]);1590}1591 1592// Checks that a memmove instruction is mapped to an illegal value when1593// specified.1594TEST(IRInstructionMapper, MemMoveIllegal) {1595 StringRef ModuleString = R"(1596 declare void @llvm.memmove.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)1597 1598 define i64 @function(i64 %x, i64 %z, i64 %n) {1599 entry:1600 %pool = alloca [59 x i64], align 41601 %tmp = bitcast [59 x i64]* %pool to i8*1602 call void @llvm.memmove.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)1603 %cmp3 = icmp eq i64 %n, 01604 %a = add i64 %x, %z1605 %c = add i64 %x, %z1606 ret i64 01607 })";1608 LLVMContext Context;1609 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1610 1611 std::vector<IRInstructionData *> InstrList;1612 std::vector<unsigned> UnsignedVec;1613 1614 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1615 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1616 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1617 Mapper.InstClassifier.EnableIntrinsics = false;1618 getVectors(*M, Mapper, InstrList, UnsignedVec);1619 1620 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1621 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));1622 ASSERT_LT(UnsignedVec[2], UnsignedVec[0]);1623}1624 1625// Checks that mem* instructions are mapped to an legal value when not1626// specified, and that all the intrinsics are marked differently.1627TEST(IRInstructionMapper, MemOpsLegal) {1628 StringRef ModuleString = R"(1629 declare void @llvm.memmove.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)1630 declare void @llvm.memcpy.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)1631 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)1632 1633 define i64 @function(i64 %x, i64 %z, i64 %n) {1634 entry:1635 %pool = alloca [59 x i64], align 41636 %tmp = bitcast [59 x i64]* %pool to i8*1637 call void @llvm.memmove.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)1638 call void @llvm.memcpy.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)1639 call void @llvm.memset.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)1640 %cmp3 = icmp eq i64 %n, 01641 %a = add i64 %x, %z1642 %c = add i64 %x, %z1643 ret i64 01644 })";1645 LLVMContext Context;1646 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1647 1648 std::vector<IRInstructionData *> InstrList;1649 std::vector<unsigned> UnsignedVec;1650 1651 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1652 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1653 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1654 Mapper.InstClassifier.EnableIntrinsics = true;1655 getVectors(*M, Mapper, InstrList, UnsignedVec);1656 1657 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1658 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(9));1659 ASSERT_LT(UnsignedVec[2], UnsignedVec[3]);1660 ASSERT_LT(UnsignedVec[3], UnsignedVec[4]);1661 ASSERT_LT(UnsignedVec[4], UnsignedVec[5]);1662}1663 1664// Checks that a variable argument instructions are mapped to an illegal value.1665// We exclude variable argument instructions since variable arguments1666// requires extra checking of the argument list.1667TEST(IRInstructionMapper, VarArgsIllegal) {1668 StringRef ModuleString = R"(1669 declare void @llvm.va_start(i8*)1670 declare void @llvm.va_copy(i8*, i8*)1671 declare void @llvm.va_end(i8*)1672 1673 define i32 @func1(i32 %a, double %b, i8* %v, ...) nounwind {1674 entry:1675 %a.addr = alloca i32, align 41676 %b.addr = alloca double, align 81677 %ap = alloca i8*, align 41678 %c = alloca i32, align 41679 store i32 %a, i32* %a.addr, align 41680 store double %b, double* %b.addr, align 81681 %ap1 = bitcast i8** %ap to i8*1682 call void @llvm.va_start(i8* %ap1)1683 store double %b, double* %b.addr, align 81684 store double %b, double* %b.addr, align 81685 %0 = va_arg i8** %ap, i321686 store double %b, double* %b.addr, align 81687 store double %b, double* %b.addr, align 81688 call void @llvm.va_copy(i8* %v, i8* %ap1)1689 store double %b, double* %b.addr, align 81690 store double %b, double* %b.addr, align 81691 call void @llvm.va_end(i8* %ap1)1692 store i32 %0, i32* %c, align 41693 %tmp = load i32, i32* %c, align 41694 ret i32 %tmp1695 })";1696 LLVMContext Context;1697 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1698 1699 std::vector<IRInstructionData *> InstrList;1700 std::vector<unsigned> UnsignedVec;1701 1702 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1703 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1704 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1705 Mapper.InstClassifier.EnableIntrinsics = false;1706 getVectors(*M, Mapper, InstrList, UnsignedVec);1707 1708 ASSERT_EQ(InstrList.size(), UnsignedVec.size());1709 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(17));1710 ASSERT_TRUE(UnsignedVec[7] < UnsignedVec[0]);1711 ASSERT_TRUE(UnsignedVec[13] < UnsignedVec[10]);1712 ASSERT_TRUE(UnsignedVec[16] < UnsignedVec[13]);1713}1714 1715// Check the length of adding two illegal instructions one after th other. We1716// should find that only one element is added for each illegal range.1717TEST(IRInstructionMapper, RepeatedIllegalLength) {1718 StringRef ModuleString = R"(1719 define i32 @f(i32 %a, i32 %b) {1720 bb0:1721 %0 = add i32 %a, %b1722 %1 = mul i32 %a, %b1723 %2 = alloca i321724 %3 = alloca i321725 %4 = add i32 %a, %b1726 %5 = mul i32 %a, %b1727 ret i32 01728 })";1729 LLVMContext Context;1730 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1731 1732 std::vector<IRInstructionData *> InstrList;1733 std::vector<unsigned> UnsignedVec;1734 1735 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1736 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1737 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1738 getVectors(*M, Mapper, InstrList, UnsignedVec);1739 1740 // Check that the size of the unsigned vector and the instruction list are the1741 // same as a safety check.1742 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1743 1744 // Make sure that the unsigned vector is the expected size.1745 ASSERT_TRUE(UnsignedVec.size() == 6);1746}1747 1748// A helper function that accepts an instruction list from a module made up of1749// two blocks of two legal instructions and terminator, and checks them for1750// instruction similarity.1751static bool longSimCandCompare(std::vector<IRInstructionData *> &InstrList,1752 bool Structure = false, unsigned Length = 2,1753 unsigned StartIdxOne = 0,1754 unsigned StartIdxTwo = 3) {1755 std::vector<IRInstructionData *>::iterator Start, End;1756 1757 Start = InstrList.begin();1758 End = InstrList.begin();1759 1760 std::advance(End, StartIdxOne + Length - 1);1761 IRSimilarityCandidate Cand1(StartIdxOne, Length, *Start, *End);1762 1763 Start = InstrList.begin();1764 End = InstrList.begin();1765 1766 std::advance(Start, StartIdxTwo);1767 std::advance(End, StartIdxTwo + Length - 1);1768 IRSimilarityCandidate Cand2(StartIdxTwo, Length, *Start, *End);1769 if (Structure)1770 return IRSimilarityCandidate::compareStructure(Cand1, Cand2);1771 return IRSimilarityCandidate::isSimilar(Cand1, Cand2);1772}1773 1774// Checks that two adds with commuted operands are considered to be the same1775// instructions.1776TEST(IRSimilarityCandidate, CheckIdenticalInstructions) {1777 StringRef ModuleString = R"(1778 define i32 @f(i32 %a, i32 %b) {1779 bb0:1780 %0 = add i32 %a, %b1781 %1 = add i32 %b, %a1782 ret i32 01783 })";1784 LLVMContext Context;1785 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1786 1787 std::vector<IRInstructionData *> InstrList;1788 std::vector<unsigned> UnsignedVec;1789 1790 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1791 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1792 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1793 getVectors(*M, Mapper, InstrList, UnsignedVec);1794 1795 // Check to make sure that we have a long enough region.1796 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(3));1797 // Check that the instructions were added correctly to both vectors.1798 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1799 1800 std::vector<IRInstructionData *>::iterator Start, End;1801 Start = InstrList.begin();1802 End = InstrList.begin();1803 std::advance(End, 1);1804 IRSimilarityCandidate Cand1(0, 2, *Start, *End);1805 IRSimilarityCandidate Cand2(0, 2, *Start, *End);1806 1807 ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));1808}1809 1810// Checks that comparison instructions are found to be similar instructions1811// when the operands are flipped and the predicate is also swapped.1812TEST(IRSimilarityCandidate, PredicateIsomorphism) {1813 StringRef ModuleString = R"(1814 define i32 @f(i32 %a, i32 %b) {1815 bb0:1816 %0 = icmp sgt i32 %a, %b1817 %1 = add i32 %b, %a1818 br label %bb11819 bb1:1820 %2 = icmp slt i32 %a, %b1821 %3 = add i32 %a, %b1822 ret i32 01823 })";1824 LLVMContext Context;1825 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1826 1827 std::vector<IRInstructionData *> InstrList;1828 std::vector<unsigned> UnsignedVec;1829 1830 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1831 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1832 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1833 getVectors(*M, Mapper, InstrList, UnsignedVec);1834 1835 ASSERT_TRUE(InstrList.size() > 5);1836 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1837 1838 std::vector<IRInstructionData *>::iterator Start, End;1839 Start = InstrList.begin();1840 End = InstrList.begin();1841 1842 std::advance(End, 1);1843 IRSimilarityCandidate Cand1(0, 2, *Start, *End);1844 1845 Start = InstrList.begin();1846 End = InstrList.begin();1847 1848 std::advance(Start, 3);1849 std::advance(End, 4);1850 IRSimilarityCandidate Cand2(3, 2, *Start, *End);1851 1852 ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));1853}1854 1855// Checks that IRSimilarityCandidates wrapping these two regions of instructions1856// are able to differentiate between instructions that have different opcodes.1857TEST(IRSimilarityCandidate, CheckRegionsDifferentInstruction) {1858 StringRef ModuleString = R"(1859 define i32 @f(i32 %a, i32 %b) {1860 bb0:1861 %0 = add i32 %a, %b1862 %1 = add i32 %b, %a1863 ret i32 01864 bb1:1865 %2 = sub i32 %a, %b1866 %3 = add i32 %b, %a1867 ret i32 01868 })";1869 LLVMContext Context;1870 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1871 1872 std::vector<IRInstructionData *> InstrList;1873 std::vector<unsigned> UnsignedVec;1874 1875 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1876 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1877 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1878 getVectors(*M, Mapper, InstrList, UnsignedVec);1879 1880 // Check to make sure that we have a long enough region.1881 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));1882 // Check that the instructions were added correctly to both vectors.1883 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1884 1885 ASSERT_FALSE(longSimCandCompare(InstrList));1886}1887 1888// Checks that IRSimilarityCandidates wrapping these two regions of instructions1889// are able to differentiate between instructions that have different types.1890TEST(IRSimilarityCandidate, CheckRegionsDifferentTypes) {1891 StringRef ModuleString = R"(1892 define i32 @f(i32 %a, i32 %b, i64 %c, i64 %d) {1893 bb0:1894 %0 = add i32 %a, %b1895 %1 = add i32 %b, %a1896 ret i32 01897 bb1:1898 %2 = add i64 %c, %d1899 %3 = add i64 %d, %c1900 ret i32 01901 })";1902 LLVMContext Context;1903 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1904 1905 std::vector<IRInstructionData *> InstrList;1906 std::vector<unsigned> UnsignedVec;1907 1908 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1909 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1910 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1911 getVectors(*M, Mapper, InstrList, UnsignedVec);1912 1913 // Check to make sure that we have a long enough region.1914 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));1915 // Check that the instructions were added correctly to both vectors.1916 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1917 1918 ASSERT_FALSE(longSimCandCompare(InstrList));1919}1920 1921// Check that debug records do not impact similarity. They are marked as1922// invisible.1923TEST(IRSimilarityCandidate, IdenticalWithDebug) {1924 StringRef ModuleString = R"(1925 define i32 @f(i32 %a, i32 %b) {1926 bb0:1927 %0 = add i32 %a, %b1928 #dbg_value(i32 0, !0, !0, !0)1929 %1 = add i32 %b, %a1930 ret i32 01931 bb1:1932 %2 = add i32 %a, %b1933 #dbg_value(i32 1, !1, !1, !1)1934 %3 = add i32 %b, %a1935 ret i32 01936 bb2:1937 %4 = add i32 %a, %b1938 %5 = add i32 %b, %a1939 ret i32 0 1940 }1941 1942 !0 = distinct !{!"test\00", i32 10}1943 !1 = distinct !{!"test\00", i32 11})";1944 LLVMContext Context;1945 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1946 1947 std::vector<IRInstructionData *> InstrList;1948 std::vector<unsigned> UnsignedVec;1949 1950 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1951 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1952 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1953 getVectors(*M, Mapper, InstrList, UnsignedVec);1954 1955 // Check to make sure that we have a long enough region.1956 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(9));1957 // Check that the instructions were added correctly to both vectors.1958 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1959 1960 ASSERT_TRUE(longSimCandCompare(InstrList));1961}1962 1963// Checks that IRSimilarityCandidates that include illegal instructions, are not1964// considered to be the same set of instructions. In these sets of instructions1965// the allocas are illegal.1966TEST(IRSimilarityCandidate, IllegalInCandidate) {1967 StringRef ModuleString = R"(1968 define i32 @f(i32 %a, i32 %b) {1969 bb0:1970 %0 = add i32 %a, %b1971 %1 = add i32 %a, %b1972 %2 = alloca i321973 ret i32 01974 bb1:1975 %3 = add i32 %a, %b1976 %4 = add i32 %a, %b1977 %5 = alloca i321978 ret i32 01979 })";1980 LLVMContext Context;1981 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);1982 1983 std::vector<IRInstructionData *> InstrList;1984 std::vector<unsigned> UnsignedVec;1985 1986 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;1987 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;1988 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);1989 getVectors(*M, Mapper, InstrList, UnsignedVec);1990 1991 // Check to make sure that we have a long enough region.1992 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));1993 // Check that the instructions were added correctly to both vectors.1994 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());1995 1996 std::vector<IRInstructionData *>::iterator Start, End;1997 1998 Start = InstrList.begin();1999 End = InstrList.begin();2000 2001 std::advance(End, 2);2002 IRSimilarityCandidate Cand1(0, 3, *Start, *End);2003 2004 Start = InstrList.begin();2005 End = InstrList.begin();2006 2007 std::advance(Start, 3);2008 std::advance(End, 5);2009 IRSimilarityCandidate Cand2(3, 3, *Start, *End);2010 ASSERT_FALSE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));2011}2012 2013// Checks that different structure, in this case, where we introduce a new2014// needed input in one region, is recognized as different.2015TEST(IRSimilarityCandidate, DifferentStructure) {2016 StringRef ModuleString = R"(2017 define i32 @f(i32 %a, i32 %b) {2018 bb0:2019 %0 = add i32 %a, %b2020 %1 = add i32 %b, %a2021 ret i32 02022 bb1:2023 %2 = add i32 %a, %b2024 %3 = add i32 %b, %02025 ret i32 02026 })";2027 LLVMContext Context;2028 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2029 2030 std::vector<IRInstructionData *> InstrList;2031 std::vector<unsigned> UnsignedVec;2032 2033 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2034 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2035 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2036 getVectors(*M, Mapper, InstrList, UnsignedVec);2037 2038 // Check to make sure that we have a long enough region.2039 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));2040 // Check that the instructions were added correctly to both vectors.2041 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2042 2043 ASSERT_FALSE(longSimCandCompare(InstrList, true));2044}2045 2046// Checks that comparison instructions are found to have the same structure2047// when the operands are flipped and the predicate is also swapped.2048TEST(IRSimilarityCandidate, PredicateIsomorphismStructure) {2049 StringRef ModuleString = R"(2050 define i32 @f(i32 %a, i32 %b) {2051 bb0:2052 %0 = icmp sgt i32 %a, %b2053 %1 = add i32 %a, %b2054 br label %bb12055 bb1:2056 %2 = icmp slt i32 %b, %a2057 %3 = add i32 %a, %b2058 ret i32 02059 })";2060 LLVMContext Context;2061 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2062 2063 std::vector<IRInstructionData *> InstrList;2064 std::vector<unsigned> UnsignedVec;2065 2066 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2067 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2068 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2069 getVectors(*M, Mapper, InstrList, UnsignedVec);2070 2071 ASSERT_TRUE(InstrList.size() > 5);2072 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2073 2074 ASSERT_TRUE(longSimCandCompare(InstrList, true));2075}2076 2077// Checks that different predicates are counted as diferent.2078TEST(IRSimilarityCandidate, PredicateDifference) {2079 StringRef ModuleString = R"(2080 define i32 @f(i32 %a, i32 %b) {2081 bb0:2082 %0 = icmp sge i32 %a, %b2083 %1 = add i32 %b, %a2084 br label %bb12085 bb1:2086 %2 = icmp slt i32 %b, %a2087 %3 = add i32 %a, %b2088 ret i32 02089 })";2090 LLVMContext Context;2091 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2092 2093 std::vector<IRInstructionData *> InstrList;2094 std::vector<unsigned> UnsignedVec;2095 2096 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2097 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2098 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2099 getVectors(*M, Mapper, InstrList, UnsignedVec);2100 2101 ASSERT_TRUE(InstrList.size() > 5);2102 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2103 2104 ASSERT_FALSE(longSimCandCompare(InstrList));2105}2106 2107// Checks that the same structure is recognized between two candidates. The2108// items %a and %b are used in the same way in both sets of instructions.2109TEST(IRSimilarityCandidate, SameStructure) {2110 StringRef ModuleString = R"(2111 define i32 @f(i32 %a, i32 %b) {2112 bb0:2113 %0 = add i32 %a, %b2114 %1 = sub i32 %b, %a2115 ret i32 02116 bb1:2117 %2 = add i32 %a, %b2118 %3 = sub i32 %b, %a2119 ret i32 02120 })";2121 LLVMContext Context;2122 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2123 2124 std::vector<IRInstructionData *> InstrList;2125 std::vector<unsigned> UnsignedVec;2126 2127 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2128 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2129 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2130 getVectors(*M, Mapper, InstrList, UnsignedVec);2131 2132 // Check to make sure that we have a long enough region.2133 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));2134 // Check that the instructions were added correctly to both vectors.2135 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2136 2137 ASSERT_TRUE(longSimCandCompare(InstrList, true));2138}2139 2140// Checks that the canonical numbering between two candidates matches the found2141// mapping between two candidates.2142TEST(IRSimilarityCandidate, CanonicalNumbering) {2143 StringRef ModuleString = R"(2144 define i32 @f(i32 %a, i32 %b) {2145 bb0:2146 %0 = add i32 %a, %b2147 %1 = sub i32 %b, %a2148 ret i32 02149 bb1:2150 %2 = add i32 %a, %b2151 %3 = sub i32 %b, %a2152 ret i32 02153 })";2154 LLVMContext Context;2155 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2156 2157 std::vector<IRInstructionData *> InstrList;2158 std::vector<unsigned> UnsignedVec;2159 2160 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2161 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2162 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2163 getVectors(*M, Mapper, InstrList, UnsignedVec);2164 2165 // Check to make sure that we have a long enough region.2166 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));2167 // Check that the instructions were added correctly to both vectors.2168 ASSERT_EQ(InstrList.size(), UnsignedVec.size());2169 2170 std::vector<IRInstructionData *>::iterator Start, End;2171 2172 Start = InstrList.begin();2173 End = InstrList.begin();2174 2175 std::advance(End, 1);2176 IRSimilarityCandidate Cand1(0, 2, *Start, *End);2177 2178 Start = InstrList.begin();2179 End = InstrList.begin();2180 2181 std::advance(Start, 3);2182 std::advance(End, 4);2183 IRSimilarityCandidate Cand2(3, 2, *Start, *End);2184 DenseMap<unsigned, DenseSet<unsigned>> Mapping1;2185 DenseMap<unsigned, DenseSet<unsigned>> Mapping2;2186 ASSERT_TRUE(IRSimilarityCandidate::compareStructure(Cand1, Cand2, Mapping1,2187 Mapping2));2188 IRSimilarityCandidate::createCanonicalMappingFor(Cand1);2189 Cand2.createCanonicalRelationFrom(Cand1, Mapping1, Mapping2);2190 2191 for (std::pair<unsigned, DenseSet<unsigned>> &P : Mapping2) {2192 unsigned Source = P.first;2193 2194 ASSERT_TRUE(Cand2.getCanonicalNum(Source).has_value());2195 unsigned Canon = *Cand2.getCanonicalNum(Source);2196 ASSERT_TRUE(Cand1.fromCanonicalNum(Canon).has_value());2197 unsigned Dest = *Cand1.fromCanonicalNum(Canon);2198 2199 DenseSet<unsigned>::iterator It = P.second.find(Dest);2200 ASSERT_NE(It, P.second.end());2201 }2202}2203 2204// Checks that the same structure is recognized between two candidates. While2205// the input names are reversed, they still perform the same overall operation.2206TEST(IRSimilarityCandidate, DifferentNameSameStructure) {2207 StringRef ModuleString = R"(2208 define i32 @f(i32 %a, i32 %b) {2209 bb0:2210 %0 = add i32 %a, %b2211 %1 = add i32 %b, %a2212 ret i32 02213 bb1:2214 %2 = add i32 %b, %a2215 %3 = add i32 %a, %b2216 ret i32 02217 })";2218 LLVMContext Context;2219 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2220 2221 std::vector<IRInstructionData *> InstrList;2222 std::vector<unsigned> UnsignedVec;2223 2224 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2225 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2226 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2227 getVectors(*M, Mapper, InstrList, UnsignedVec);2228 2229 // Check to make sure that we have a long enough region.2230 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));2231 // Check that the instructions were added correctly to both vectors.2232 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2233 2234 ASSERT_TRUE(longSimCandCompare(InstrList, true));2235}2236 2237// Checks that the same structure is recognized between two candidates when2238// the branches target other blocks inside the same region, the relative2239// distance between the blocks must be the same.2240TEST(IRSimilarityCandidate, SameBranchStructureInternal) {2241 StringRef ModuleString = R"(2242 define i32 @f(i32 %a, i32 %b) {2243 bb0:2244 %0 = add i32 %a, %b2245 %1 = add i32 %b, %a2246 br label %bb12247 bb1:2248 %2 = add i32 %b, %a2249 %3 = add i32 %a, %b2250 ret i32 02251 }2252 2253 define i32 @f2(i32 %a, i32 %b) {2254 bb0:2255 %0 = add i32 %a, %b2256 %1 = add i32 %b, %a2257 br label %bb12258 bb1:2259 %2 = add i32 %b, %a2260 %3 = add i32 %a, %b2261 ret i32 02262 })";2263 LLVMContext Context;2264 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2265 2266 std::vector<IRInstructionData *> InstrList;2267 std::vector<unsigned> UnsignedVec;2268 2269 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2270 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2271 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2272 Mapper.InstClassifier.EnableBranches = true;2273 Mapper.initializeForBBs(*M);2274 getVectors(*M, Mapper, InstrList, UnsignedVec);2275 2276 // Check to make sure that we have a long enough region.2277 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));2278 // Check that the instructions were added correctly to both vectors.2279 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2280 2281 ASSERT_TRUE(longSimCandCompare(InstrList, true, 5, 0, 6));2282}2283 2284// Checks that the different structure is recognized between two candidates,2285// when the branches target other blocks inside the same region, the relative2286// distance between the blocks must be the same.2287TEST(IRSimilarityCandidate, DifferentBranchStructureInternal) {2288 StringRef ModuleString = R"(2289 define i32 @f(i32 %a, i32 %b) {2290 bb0:2291 %0 = add i32 %a, %b2292 %1 = add i32 %b, %a2293 br label %bb22294 bb1:2295 %2 = add i32 %b, %a2296 %3 = add i32 %a, %b2297 br label %bb22298 bb2:2299 %4 = add i32 %b, %a2300 %5 = add i32 %a, %b2301 ret i32 02302 }2303 2304 define i32 @f2(i32 %a, i32 %b) {2305 bb0:2306 %0 = add i32 %a, %b2307 %1 = add i32 %b, %a2308 br label %bb12309 bb1:2310 %2 = add i32 %b, %a2311 %3 = add i32 %a, %b2312 br label %bb22313 bb2:2314 %4 = add i32 %b, %a2315 %5 = add i32 %a, %b2316 ret i32 02317 })";2318 LLVMContext Context;2319 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2320 2321 std::vector<IRInstructionData *> InstrList;2322 std::vector<unsigned> UnsignedVec;2323 2324 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2325 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2326 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2327 Mapper.InstClassifier.EnableBranches = true;2328 Mapper.initializeForBBs(*M);2329 getVectors(*M, Mapper, InstrList, UnsignedVec);2330 2331 // Check to make sure that we have a long enough region.2332 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(18));2333 // Check that the instructions were added correctly to both vectors.2334 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2335 2336 ASSERT_FALSE(longSimCandCompare(InstrList, true, 6, 0, 9));2337}2338 2339// Checks that the same structure is recognized between two candidates, when2340// the branches target other blocks outside region, the relative distance2341// does not need to be the same.2342TEST(IRSimilarityCandidate, SameBranchStructureOutside) {2343 StringRef ModuleString = R"(2344 define i32 @f(i32 %a, i32 %b) {2345 bb0:2346 %0 = add i32 %a, %b2347 %1 = add i32 %b, %a2348 br label %bb12349 bb1:2350 %2 = add i32 %b, %a2351 %3 = add i32 %a, %b2352 ret i32 02353 }2354 2355 define i32 @f2(i32 %a, i32 %b) {2356 bb0:2357 %0 = add i32 %a, %b2358 %1 = add i32 %b, %a2359 br label %bb12360 bb1:2361 %2 = add i32 %b, %a2362 %3 = add i32 %a, %b2363 ret i32 02364 })";2365 LLVMContext Context;2366 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2367 2368 std::vector<IRInstructionData *> InstrList;2369 std::vector<unsigned> UnsignedVec;2370 2371 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2372 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2373 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2374 Mapper.InstClassifier.EnableBranches = true;2375 Mapper.initializeForBBs(*M);2376 getVectors(*M, Mapper, InstrList, UnsignedVec);2377 2378 // Check to make sure that we have a long enough region.2379 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));2380 // Check that the instructions were added correctly to both vectors.2381 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2382 2383 ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6));2384}2385 2386// Checks that the same structure is recognized between two candidates, when2387// the branches target other blocks outside region, the relative distance2388// does not need to be the same.2389TEST(IRSimilarityCandidate, DifferentBranchStructureOutside) {2390 StringRef ModuleString = R"(2391 define i32 @f(i32 %a, i32 %b) {2392 bb0:2393 %0 = add i32 %a, %b2394 %1 = add i32 %b, %a2395 br label %bb12396 bb1:2397 %2 = add i32 %b, %a2398 %3 = add i32 %a, %b2399 ret i32 02400 }2401 2402 define i32 @f2(i32 %a, i32 %b) {2403 bb0:2404 %0 = add i32 %a, %b2405 %1 = add i32 %b, %a2406 br label %bb22407 bb1:2408 %2 = add i32 %b, %a2409 %3 = add i32 %a, %b2410 br label %bb22411 bb2:2412 %4 = add i32 %b, %a2413 %5 = add i32 %a, %b2414 ret i32 02415 })";2416 LLVMContext Context;2417 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2418 2419 std::vector<IRInstructionData *> InstrList;2420 std::vector<unsigned> UnsignedVec;2421 2422 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2423 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2424 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2425 Mapper.InstClassifier.EnableBranches = true;2426 Mapper.initializeForBBs(*M);2427 getVectors(*M, Mapper, InstrList, UnsignedVec);2428 2429 // Check to make sure that we have a long enough region.2430 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(15));2431 // Check that the instructions were added correctly to both vectors.2432 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2433 2434 ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6));2435}2436 2437// Checks that the same structure is recognized between two candidates,2438// when the phi predecessor are other blocks inside the same region,2439// the relative distance between the blocks must be the same.2440TEST(IRSimilarityCandidate, SamePHIStructureInternal) {2441 StringRef ModuleString = R"(2442 define i32 @f(i32 %a, i32 %b) {2443 bb0:2444 br label %bb22445 bb1:2446 br label %bb22447 bb2:2448 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ] 2449 %1 = add i32 %b, %a2450 %2 = add i32 %a, %b2451 ret i32 02452 }2453 2454 define i32 @f2(i32 %a, i32 %b) {2455 bb0:2456 br label %bb22457 bb1:2458 br label %bb22459 bb2:2460 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ]2461 %1 = add i32 %b, %a2462 %2 = add i32 %a, %b2463 ret i32 02464 })";2465 LLVMContext Context;2466 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2467 2468 std::vector<IRInstructionData *> InstrList;2469 std::vector<unsigned> UnsignedVec;2470 2471 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2472 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2473 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2474 Mapper.InstClassifier.EnableBranches = true;2475 Mapper.initializeForBBs(*M);2476 getVectors(*M, Mapper, InstrList, UnsignedVec);2477 2478 // Check to make sure that we have a long enough region.2479 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));2480 // Check that the instructions were added correctly to both vectors.2481 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2482 2483 ASSERT_TRUE(longSimCandCompare(InstrList, true, 4, 0, 6));2484}2485 2486// Checks that the different structure is recognized between two candidates,2487// when the phi predecessor are other blocks inside the same region,2488// the relative distance between the blocks must be the same.2489TEST(IRSimilarityCandidate, DifferentPHIStructureInternal) {2490 StringRef ModuleString = R"(2491 define i32 @f(i32 %a, i32 %b) {2492 bb0:2493 br label %bb22494 bb1:2495 br label %bb22496 bb3:2497 br label %bb22498 bb2:2499 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ] 2500 %1 = add i32 %b, %a2501 %2 = add i32 %a, %b2502 ret i32 02503 }2504 2505 define i32 @f2(i32 %a, i32 %b) {2506 bb0:2507 br label %bb22508 bb1:2509 br label %bb22510 bb3:2511 br label %bb22512 bb2:2513 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb3 ] 2514 %1 = add i32 %b, %a2515 %2 = add i32 %a, %b2516 ret i32 02517 })";2518 LLVMContext Context;2519 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2520 2521 std::vector<IRInstructionData *> InstrList;2522 std::vector<unsigned> UnsignedVec;2523 2524 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;2525 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;2526 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);2527 Mapper.InstClassifier.EnableBranches = true;2528 Mapper.initializeForBBs(*M);2529 getVectors(*M, Mapper, InstrList, UnsignedVec);2530 2531 // Check to make sure that we have a long enough region.2532 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(14));2533 // Check that the instructions were added correctly to both vectors.2534 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());2535 2536 ASSERT_FALSE(longSimCandCompare(InstrList, true, 5, 0, 7));2537}2538 2539// Checks that two sets of identical instructions are found to be the same.2540// Both sequences of adds have the same operand ordering, and the same2541// instructions, making them strcturally equivalent.2542TEST(IRSimilarityIdentifier, IdentitySimilarity) {2543 StringRef ModuleString = R"(2544 define i32 @f(i32 %a, i32 %b) {2545 bb0:2546 %0 = add i32 %a, %b2547 %1 = sub i32 %b, %a2548 br label %bb12549 bb1:2550 %2 = add i32 %a, %b2551 %3 = sub i32 %b, %a2552 ret i32 02553 })";2554 LLVMContext Context;2555 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2556 2557 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2558 getSimilarities(*M, SimilarityCandidates);2559 2560 ASSERT_TRUE(SimilarityCandidates.size() == 1);2561 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {2562 ASSERT_TRUE(Cands.size() == 2);2563 unsigned InstIdx = 0;2564 for (IRSimilarityCandidate &Cand : Cands) {2565 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);2566 InstIdx += 3;2567 }2568 }2569}2570 2571// Checks that incorrect sequences are not found as similar. In this case,2572// we have different sequences of instructions.2573TEST(IRSimilarityIdentifier, InstructionDifference) {2574 StringRef ModuleString = R"(2575 define i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) {2576 bb0:2577 %0 = sub i32 %a, %b2578 %1 = add i32 %b, %a2579 br label %bb12580 bb1:2581 %2 = add i32 %c, %d2582 %3 = sub i32 %d, %c2583 ret i32 02584 })";2585 LLVMContext Context;2586 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2587 2588 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2589 getSimilarities(*M, SimilarityCandidates);2590 2591 ASSERT_TRUE(SimilarityCandidates.empty());2592}2593 2594// This test checks to see whether we can detect similarity for commutative2595// instructions where the operands have been reversed.2596TEST(IRSimilarityIdentifier, CommutativeSimilarity) {2597 StringRef ModuleString = R"(2598 define i32 @f(i32 %a, i32 %b) {2599 bb0:2600 %0 = add i32 %a, %b2601 %1 = add i32 %b, %a2602 br label %bb12603 bb1:2604 %2 = add i32 %a, %b2605 %3 = add i32 %a, %b2606 ret i32 02607 })";2608 LLVMContext Context;2609 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2610 2611 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2612 getSimilarities(*M, SimilarityCandidates);2613 2614 ASSERT_TRUE(SimilarityCandidates.size() == 1);2615 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {2616 ASSERT_TRUE(Cands.size() == 2);2617 unsigned InstIdx = 0;2618 for (IRSimilarityCandidate &Cand : Cands) {2619 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);2620 InstIdx += 3;2621 }2622 }2623}2624 2625// This test ensures that when the first instruction in a sequence is2626// a commutative instruction with the same value (mcomm_inst_same_val), but the2627// corresponding instruction (comm_inst_diff_val) is not, we mark the regions2628// and not similar.2629TEST(IRSimilarityIdentifier, CommutativeSameValueFirstMisMatch) {2630 StringRef ModuleString = R"(2631 define void @v_1_0(i64 %v_33) {2632 entry:2633 %comm_inst_same_val = mul i64 undef, undef2634 %add = add i64 %comm_inst_same_val, %v_332635 %comm_inst_diff_val = mul i64 0, undef2636 %mul.i = add i64 %comm_inst_diff_val, %comm_inst_diff_val2637 unreachable2638 })";2639 LLVMContext Context;2640 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2641 2642 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2643 getSimilarities(*M, SimilarityCandidates);2644 2645 ASSERT_TRUE(SimilarityCandidates.size() == 0);2646}2647 2648// This test makes sure that intrinsic functions that are marked commutative2649// are still treated as non-commutative since they are function calls.2650TEST(IRSimilarityIdentifier, IntrinsicCommutative) {2651 // If treated as commutative, we will fail to find a valid mapping, causing2652 // an assertion error.2653 StringRef ModuleString = R"(2654 define void @foo() {2655 entry:2656 %0 = call i16 @llvm.smul.fix.i16(i16 16384, i16 16384, i32 15)2657 store i16 %0, i16* undef, align 12658 %1 = icmp eq i16 undef, 81922659 call void @bar()2660 %2 = call i16 @llvm.smul.fix.i16(i16 -16384, i16 16384, i32 15)2661 store i16 %2, i16* undef, align 12662 %3 = icmp eq i16 undef, -81922663 call void @bar()2664 %4 = call i16 @llvm.smul.fix.i16(i16 -16384, i16 -16384, i32 15)2665 ret void2666 }2667 2668 declare void @bar()2669 2670 ; Function Attrs: nofree nosync nounwind readnone speculatable willreturn2671 declare i16 @llvm.smul.fix.i16(i16, i16, i32 immarg))";2672 LLVMContext Context;2673 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2674 2675 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2676 getSimilarities(*M, SimilarityCandidates);2677 2678 ASSERT_TRUE(SimilarityCandidates.size() == 0);2679}2680 2681// This test checks to see whether we can detect different structure in2682// commutative instructions. In this case, the second operand in the second2683// add is different.2684TEST(IRSimilarityIdentifier, NoCommutativeSimilarity) {2685 StringRef ModuleString = R"(2686 define i32 @f(i32 %a, i32 %b) {2687 bb0:2688 %0 = add i32 %a, %b2689 %1 = add i32 %1, %b2690 br label %bb12691 bb1:2692 %2 = add i32 %a, %b2693 %3 = add i32 %2, %a2694 ret i32 02695 })";2696 LLVMContext Context;2697 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2698 2699 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2700 getSimilarities(*M, SimilarityCandidates);2701 2702 ASSERT_TRUE(SimilarityCandidates.size() == 0);2703}2704 2705// Check that we are not finding similarity in non commutative2706// instructions. That is, while the instruction and operands used are the same2707// in the two subtraction sequences, they are in a different order, and cannot2708// be counted as the same since a subtraction is not commutative.2709TEST(IRSimilarityIdentifier, NonCommutativeDifference) {2710 StringRef ModuleString = R"(2711 define i32 @f(i32 %a, i32 %b) {2712 bb0:2713 %0 = sub i32 %a, %b2714 %1 = sub i32 %b, %a2715 br label %bb12716 bb1:2717 %2 = sub i32 %a, %b2718 %3 = sub i32 %a, %b2719 ret i32 02720 })";2721 LLVMContext Context;2722 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2723 2724 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2725 getSimilarities(*M, SimilarityCandidates);2726 2727 ASSERT_TRUE(SimilarityCandidates.empty());2728}2729 2730// Check that we find similarity despite changing the register names.2731TEST(IRSimilarityIdentifier, MappingSimilarity) {2732 StringRef ModuleString = R"(2733 define i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) {2734 bb0:2735 %0 = add i32 %a, %b2736 %1 = sub i32 %b, %a2737 br label %bb12738 bb1:2739 %2 = add i32 %c, %d2740 %3 = sub i32 %d, %c2741 ret i32 02742 })";2743 LLVMContext Context;2744 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2745 2746 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2747 getSimilarities(*M, SimilarityCandidates);2748 2749 ASSERT_TRUE(SimilarityCandidates.size() == 1);2750 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {2751 ASSERT_TRUE(Cands.size() == 2);2752 unsigned InstIdx = 0;2753 for (IRSimilarityCandidate &Cand : Cands) {2754 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);2755 InstIdx += 3;2756 }2757 }2758}2759 2760// Check that we find instances of swapped predicate isomorphism. That is,2761// for predicates that can be flipped, e.g. greater than to less than,2762// we can identify that instances of these different literal predicates, but are2763// the same within a single swap can be found.2764TEST(IRSimilarityIdentifier, PredicateIsomorphism) {2765 StringRef ModuleString = R"(2766 define i32 @f(i32 %a, i32 %b) {2767 bb0:2768 %0 = add i32 %a, %b2769 %1 = icmp sgt i32 %b, %a2770 br label %bb12771 bb1:2772 %2 = add i32 %a, %b2773 %3 = icmp slt i32 %a, %b2774 ret i32 02775 })";2776 LLVMContext Context;2777 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2778 2779 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2780 getSimilarities(*M, SimilarityCandidates);2781 2782 ASSERT_TRUE(SimilarityCandidates.size() == 1);2783 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {2784 ASSERT_TRUE(Cands.size() == 2);2785 unsigned InstIdx = 0;2786 for (IRSimilarityCandidate &Cand : Cands) {2787 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);2788 InstIdx += 3;2789 }2790 }2791}2792 2793// Checks that constants are detected as the same operand in each use in the2794// sequences of instructions. Also checks that we can find structural2795// equivalence using constants. In this case the 1 has the same use pattern as2796// %a.2797TEST(IRSimilarityIdentifier, ConstantMappingSimilarity) {2798 StringRef ModuleString = R"(2799 define i32 @f(i32 %a, i32 %b) {2800 bb0:2801 %0 = add i32 1, %b2802 %1 = icmp sgt i32 %b, 12803 br label %bb12804 bb1:2805 %2 = add i32 %a, %b2806 %3 = icmp sgt i32 %b, %a2807 ret i32 02808 })";2809 LLVMContext Context;2810 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2811 2812 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2813 getSimilarities(*M, SimilarityCandidates);2814 2815 ASSERT_TRUE(SimilarityCandidates.size() == 1);2816 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {2817 ASSERT_TRUE(Cands.size() == 2);2818 unsigned InstIdx = 0;2819 for (IRSimilarityCandidate &Cand : Cands) {2820 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);2821 InstIdx += 3;2822 }2823 }2824}2825 2826// Check that constants are uniquely identified. i.e. two different constants2827// are not considered the same. This means that this should not find any2828// structural similarity.2829TEST(IRSimilarityIdentifier, ConstantMappingDifference) {2830 StringRef ModuleString = R"(2831 define i32 @f(i32 %a, i32 %b) {2832 bb0:2833 %0 = add i32 1, %b2834 %1 = icmp sgt i32 %b, 22835 br label %bb12836 bb1:2837 %2 = add i32 %a, %b2838 %3 = icmp slt i32 %a, %b2839 ret i32 02840 })";2841 LLVMContext Context;2842 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);2843 2844 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;2845 getSimilarities(*M, SimilarityCandidates);2846 2847 ASSERT_TRUE(SimilarityCandidates.empty());2848}2849