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-exception
6 //
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/SourceMgr.h"
21 #include "gtest/gtest.h"
22
23 using namespace llvm;
24 using namespace IRSimilarity;
25
26 extern llvm::cl::opt<bool> UseNewDbgInfoFormat;
27 extern cl::opt<cl::boolOrDefault> PreserveInputDbgFormat;
28 extern bool WriteNewDbgInfoFormatToBitcode;
29 extern cl::opt<bool> WriteNewDbgInfoFormat;
30
makeLLVMModule(LLVMContext & Context,StringRef ModuleStr)31 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
32 StringRef ModuleStr) {
33 SMDiagnostic Err;
34 std::unique_ptr<Module> M = parseAssemblyString(ModuleStr, Err, Context);
35 assert(M && "Bad LLVM IR?");
36 return M;
37 }
38
getVectors(Module & M,IRInstructionMapper & Mapper,std::vector<IRInstructionData * > & InstrList,std::vector<unsigned> & UnsignedVec)39 void getVectors(Module &M, IRInstructionMapper &Mapper,
40 std::vector<IRInstructionData *> &InstrList,
41 std::vector<unsigned> &UnsignedVec) {
42 for (Function &F : M)
43 for (BasicBlock &BB : F)
44 Mapper.convertToUnsignedVec(BB, InstrList, UnsignedVec);
45 }
46
getSimilarities(Module & M,std::vector<std::vector<IRSimilarityCandidate>> & SimilarityCandidates)47 void getSimilarities(
48 Module &M,
49 std::vector<std::vector<IRSimilarityCandidate>> &SimilarityCandidates) {
50 // In order to keep the size of the tests from becoming too large, we do not
51 // recognize similarity for branches unless explicitly needed.
52 IRSimilarityIdentifier Identifier(/*EnableBranchMatching = */false);
53 SimilarityCandidates = Identifier.findSimilarity(M);
54 }
55
56 // Checks that different opcodes are mapped to different values
TEST(IRInstructionMapper,OpcodeDifferentiation)57 TEST(IRInstructionMapper, OpcodeDifferentiation) {
58 StringRef ModuleString = R"(
59 define i32 @f(i32 %a, i32 %b) {
60 bb0:
61 %0 = add i32 %a, %b
62 %1 = mul i32 %a, %b
63 ret i32 0
64 })";
65 LLVMContext Context;
66 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
67
68 std::vector<IRInstructionData *> InstrList;
69 std::vector<unsigned> UnsignedVec;
70
71 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
72 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
73 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
74 getVectors(*M, Mapper, InstrList, UnsignedVec);
75
76 // Check that the size of the unsigned vector and the instruction list are the
77 // same as a safety check.
78 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
79
80 // Make sure that the unsigned vector is the expected size.
81 ASSERT_TRUE(UnsignedVec.size() == 3);
82
83 // Check whether the instructions are not mapped to the same value.
84 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
85 }
86
87 // Checks that the same opcodes and types are mapped to the same values.
TEST(IRInstructionMapper,OpcodeTypeSimilarity)88 TEST(IRInstructionMapper, OpcodeTypeSimilarity) {
89 StringRef ModuleString = R"(
90 define i32 @f(i32 %a, i32 %b) {
91 bb0:
92 %0 = add i32 %a, %b
93 %1 = add i32 %b, %a
94 ret i32 0
95 })";
96 LLVMContext Context;
97 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
98
99 std::vector<IRInstructionData *> InstrList;
100 std::vector<unsigned> UnsignedVec;
101
102 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
103 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
104 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
105 getVectors(*M, Mapper, InstrList, UnsignedVec);
106
107 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
108 ASSERT_TRUE(UnsignedVec.size() == 3);
109
110 // Check whether the instructions are mapped to the same value.
111 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
112 }
113
114 // Checks that the same opcode and different types are mapped to different
115 // values.
TEST(IRInstructionMapper,TypeDifferentiation)116 TEST(IRInstructionMapper, TypeDifferentiation) {
117 StringRef ModuleString = R"(
118 define i32 @f(i32 %a, i32 %b, i64 %c, i64 %d) {
119 bb0:
120 %0 = add i32 %a, %b
121 %1 = add i64 %c, %d
122 ret i32 0
123 })";
124 LLVMContext Context;
125 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
126
127 std::vector<IRInstructionData *> InstrList;
128 std::vector<unsigned> UnsignedVec;
129
130 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
131 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
132 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
133 getVectors(*M, Mapper, InstrList, UnsignedVec);
134
135 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
136 ASSERT_TRUE(UnsignedVec.size() == 3);
137 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
138 }
139
140 // Checks that different predicates map to different values.
TEST(IRInstructionMapper,PredicateDifferentiation)141 TEST(IRInstructionMapper, PredicateDifferentiation) {
142 StringRef ModuleString = R"(
143 define i32 @f(i32 %a, i32 %b) {
144 bb0:
145 %0 = icmp sge i32 %b, %a
146 %1 = icmp slt i32 %a, %b
147 ret i32 0
148 })";
149 LLVMContext Context;
150 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
151
152 std::vector<IRInstructionData *> InstrList;
153 std::vector<unsigned> UnsignedVec;
154
155 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
156 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
157 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
158 getVectors(*M, Mapper, InstrList, UnsignedVec);
159
160 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
161 ASSERT_TRUE(UnsignedVec.size() == 3);
162 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
163 }
164
165 // Checks that predicates where that can be considered the same when the
166 // operands are swapped, i.e. greater than to less than are mapped to the same
167 // unsigned integer.
TEST(IRInstructionMapper,PredicateIsomorphism)168 TEST(IRInstructionMapper, PredicateIsomorphism) {
169 StringRef ModuleString = R"(
170 define i32 @f(i32 %a, i32 %b) {
171 bb0:
172 %0 = icmp sgt i32 %a, %b
173 %1 = icmp slt i32 %b, %a
174 ret i32 0
175 })";
176 LLVMContext Context;
177 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
178
179 std::vector<IRInstructionData *> InstrList;
180 std::vector<unsigned> UnsignedVec;
181
182 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
183 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
184 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
185 getVectors(*M, Mapper, InstrList, UnsignedVec);
186
187 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
188 ASSERT_TRUE(UnsignedVec.size() == 3);
189 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
190 }
191
192 // Checks that the same predicate maps to the same value.
TEST(IRInstructionMapper,PredicateSimilarity)193 TEST(IRInstructionMapper, PredicateSimilarity) {
194 StringRef ModuleString = R"(
195 define i32 @f(i32 %a, i32 %b) {
196 bb0:
197 %0 = icmp slt i32 %a, %b
198 %1 = icmp slt i32 %b, %a
199 ret i32 0
200 })";
201 LLVMContext Context;
202 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
203
204 std::vector<IRInstructionData *> InstrList;
205 std::vector<unsigned> UnsignedVec;
206
207 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
208 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
209 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
210 getVectors(*M, Mapper, InstrList, UnsignedVec);
211
212 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
213 ASSERT_TRUE(UnsignedVec.size() == 3);
214 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
215 }
216
217 // Checks that the same predicate maps to the same value for floating point
218 // CmpInsts.
TEST(IRInstructionMapper,FPPredicateSimilarity)219 TEST(IRInstructionMapper, FPPredicateSimilarity) {
220 StringRef ModuleString = R"(
221 define i32 @f(double %a, double %b) {
222 bb0:
223 %0 = fcmp olt double %a, %b
224 %1 = fcmp olt double %b, %a
225 ret i32 0
226 })";
227 LLVMContext Context;
228 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
229
230 std::vector<IRInstructionData *> InstrList;
231 std::vector<unsigned> UnsignedVec;
232
233 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
234 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
235 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
236 getVectors(*M, Mapper, InstrList, UnsignedVec);
237
238 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
239 ASSERT_TRUE(UnsignedVec.size() == 3);
240 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
241 }
242
243 // Checks that the different predicate maps to a different value for floating
244 // point CmpInsts.
TEST(IRInstructionMapper,FPPredicatDifference)245 TEST(IRInstructionMapper, FPPredicatDifference) {
246 StringRef ModuleString = R"(
247 define i32 @f(double %a, double %b) {
248 bb0:
249 %0 = fcmp olt double %a, %b
250 %1 = fcmp oge double %b, %a
251 ret i32 0
252 })";
253 LLVMContext Context;
254 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
255
256 std::vector<IRInstructionData *> InstrList;
257 std::vector<unsigned> UnsignedVec;
258
259 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
260 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
261 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
262 getVectors(*M, Mapper, InstrList, UnsignedVec);
263
264 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
265 ASSERT_TRUE(UnsignedVec.size() == 3);
266 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
267 }
268
269 // Checks that the zexts that have the same type parameters map to the same
270 // unsigned integer.
TEST(IRInstructionMapper,ZextTypeSimilarity)271 TEST(IRInstructionMapper, ZextTypeSimilarity) {
272 StringRef ModuleString = R"(
273 define i32 @f(i32 %a) {
274 bb0:
275 %0 = zext i32 %a to i64
276 %1 = zext i32 %a to i64
277 ret i32 0
278 })";
279 LLVMContext Context;
280 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
281
282 std::vector<IRInstructionData *> InstrList;
283 std::vector<unsigned> UnsignedVec;
284
285 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
286 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
287 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
288 getVectors(*M, Mapper, InstrList, UnsignedVec);
289
290 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
291 ASSERT_TRUE(UnsignedVec.size() == 3);
292 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
293 }
294
295 // Checks that the sexts that have the same type parameters map to the same
296 // unsigned integer.
TEST(IRInstructionMapper,SextTypeSimilarity)297 TEST(IRInstructionMapper, SextTypeSimilarity) {
298 StringRef ModuleString = R"(
299 define i32 @f(i32 %a) {
300 bb0:
301 %0 = sext i32 %a to i64
302 %1 = sext i32 %a to i64
303 ret i32 0
304 })";
305 LLVMContext Context;
306 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
307
308 std::vector<IRInstructionData *> InstrList;
309 std::vector<unsigned> UnsignedVec;
310
311 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
312 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
313 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
314 getVectors(*M, Mapper, InstrList, UnsignedVec);
315
316 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
317 ASSERT_TRUE(UnsignedVec.size() == 3);
318 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
319 }
320
321 // Checks that the zexts that have the different type parameters map to the
322 // different unsigned integers.
TEST(IRInstructionMapper,ZextTypeDifference)323 TEST(IRInstructionMapper, ZextTypeDifference) {
324 StringRef ModuleString = R"(
325 define i32 @f(i32 %a, i8 %b) {
326 bb0:
327 %0 = zext i32 %a to i64
328 %1 = zext i8 %b to i32
329 ret i32 0
330 })";
331 LLVMContext Context;
332 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
333
334 std::vector<IRInstructionData *> InstrList;
335 std::vector<unsigned> UnsignedVec;
336
337 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
338 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
339 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
340 getVectors(*M, Mapper, InstrList, UnsignedVec);
341
342 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
343 ASSERT_TRUE(UnsignedVec.size() == 3);
344 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
345 }
346
347 // Checks that the sexts that have the different type parameters map to the
348 // different unsigned integers.
TEST(IRInstructionMapper,SextTypeDifference)349 TEST(IRInstructionMapper, SextTypeDifference) {
350 StringRef ModuleString = R"(
351 define i32 @f(i32 %a, i8 %b) {
352 bb0:
353 %0 = sext i32 %a to i64
354 %1 = sext i8 %b to i32
355 ret i32 0
356 })";
357 LLVMContext Context;
358 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
359
360 std::vector<IRInstructionData *> InstrList;
361 std::vector<unsigned> UnsignedVec;
362
363 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
364 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
365 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
366 getVectors(*M, Mapper, InstrList, UnsignedVec);
367
368 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
369 ASSERT_TRUE(UnsignedVec.size() == 3);
370 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
371 }
372
373 // Checks that loads that have the same type are mapped to the same unsigned
374 // integer.
TEST(IRInstructionMapper,LoadSimilarType)375 TEST(IRInstructionMapper, LoadSimilarType) {
376 StringRef ModuleString = R"(
377 define i32 @f(i32* %a, i32* %b) {
378 bb0:
379 %0 = load i32, i32* %a
380 %1 = load i32, i32* %b
381 ret i32 0
382 })";
383 LLVMContext Context;
384 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
385
386 std::vector<IRInstructionData *> InstrList;
387 std::vector<unsigned> UnsignedVec;
388
389 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
390 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
391 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
392 getVectors(*M, Mapper, InstrList, UnsignedVec);
393
394 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
395 ASSERT_TRUE(UnsignedVec.size() == 3);
396 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
397 }
398
399 // Checks that loads that have the different types are mapped to
400 // different unsigned integers.
TEST(IRInstructionMapper,LoadDifferentType)401 TEST(IRInstructionMapper, LoadDifferentType) {
402 StringRef ModuleString = R"(
403 define i32 @f(i32* %a, i64* %b) {
404 bb0:
405 %0 = load i32, i32* %a
406 %1 = load i64, i64* %b
407 ret i32 0
408 })";
409 LLVMContext Context;
410 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
411
412 std::vector<IRInstructionData *> InstrList;
413 std::vector<unsigned> UnsignedVec;
414
415 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
416 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
417 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
418 getVectors(*M, Mapper, InstrList, UnsignedVec);
419
420 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
421 ASSERT_TRUE(UnsignedVec.size() == 3);
422 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
423 }
424
425 // Checks that loads that have the different aligns are mapped to different
426 // unsigned integers.
TEST(IRInstructionMapper,LoadDifferentAlign)427 TEST(IRInstructionMapper, LoadDifferentAlign) {
428 StringRef ModuleString = R"(
429 define i32 @f(i32* %a, i32* %b) {
430 bb0:
431 %0 = load i32, i32* %a, align 4
432 %1 = load i32, i32* %b, align 8
433 ret i32 0
434 })";
435 LLVMContext Context;
436 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
437
438 std::vector<IRInstructionData *> InstrList;
439 std::vector<unsigned> UnsignedVec;
440
441 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
442 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
443 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
444 getVectors(*M, Mapper, InstrList, UnsignedVec);
445
446 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
447 ASSERT_TRUE(UnsignedVec.size() == 3);
448 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
449 }
450
451 // Checks that loads that have the different volatile settings are mapped to
452 // different unsigned integers.
TEST(IRInstructionMapper,LoadDifferentVolatile)453 TEST(IRInstructionMapper, LoadDifferentVolatile) {
454 StringRef ModuleString = R"(
455 define i32 @f(i32* %a, i32* %b) {
456 bb0:
457 %0 = load volatile i32, i32* %a
458 %1 = load i32, i32* %b
459 ret i32 0
460 })";
461 LLVMContext Context;
462 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
463
464 std::vector<IRInstructionData *> InstrList;
465 std::vector<unsigned> UnsignedVec;
466
467 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
468 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
469 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
470 getVectors(*M, Mapper, InstrList, UnsignedVec);
471
472 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
473 ASSERT_TRUE(UnsignedVec.size() == 3);
474 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
475 }
476
477 // Checks that loads that have the same volatile settings are mapped to
478 // different unsigned integers.
TEST(IRInstructionMapper,LoadSameVolatile)479 TEST(IRInstructionMapper, LoadSameVolatile) {
480 StringRef ModuleString = R"(
481 define i32 @f(i32* %a, i32* %b) {
482 bb0:
483 %0 = load volatile i32, i32* %a
484 %1 = load volatile i32, i32* %b
485 ret i32 0
486 })";
487 LLVMContext Context;
488 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
489
490 std::vector<IRInstructionData *> InstrList;
491 std::vector<unsigned> UnsignedVec;
492
493 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
494 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
495 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
496 getVectors(*M, Mapper, InstrList, UnsignedVec);
497
498 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
499 ASSERT_TRUE(UnsignedVec.size() == 3);
500 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
501 }
502
503 // Checks that loads that have the different atomicity settings are mapped to
504 // different unsigned integers.
TEST(IRInstructionMapper,LoadDifferentAtomic)505 TEST(IRInstructionMapper, LoadDifferentAtomic) {
506 StringRef ModuleString = R"(
507 define i32 @f(i32* %a, i32* %b) {
508 bb0:
509 %0 = load atomic i32, i32* %a unordered, align 4
510 %1 = load atomic i32, i32* %b monotonic, align 4
511 ret i32 0
512 })";
513 LLVMContext Context;
514 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
515
516 std::vector<IRInstructionData *> InstrList;
517 std::vector<unsigned> UnsignedVec;
518
519 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
520 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
521 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
522 getVectors(*M, Mapper, InstrList, UnsignedVec);
523
524 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
525 ASSERT_TRUE(UnsignedVec.size() == 3);
526 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
527 }
528
529 // Checks that loads that have the same atomicity settings are mapped to
530 // different unsigned integers.
TEST(IRInstructionMapper,LoadSameAtomic)531 TEST(IRInstructionMapper, LoadSameAtomic) {
532 StringRef ModuleString = R"(
533 define i32 @f(i32* %a, i32* %b) {
534 bb0:
535 %0 = load atomic i32, i32* %a unordered, align 4
536 %1 = load atomic i32, i32* %b unordered, align 4
537 ret i32 0
538 })";
539 LLVMContext Context;
540 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
541
542 std::vector<IRInstructionData *> InstrList;
543 std::vector<unsigned> UnsignedVec;
544
545 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
546 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
547 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
548 getVectors(*M, Mapper, InstrList, UnsignedVec);
549
550 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
551 ASSERT_TRUE(UnsignedVec.size() == 3);
552 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
553 }
554
555 // Checks that stores that have the same type are mapped to the same unsigned
556 // integer.
TEST(IRInstructionMapper,StoreSimilarType)557 TEST(IRInstructionMapper, StoreSimilarType) {
558 StringRef ModuleString = R"(
559 define i32 @f(i32* %a, i32* %b) {
560 bb0:
561 store i32 1, i32* %a
562 store i32 2, i32* %a
563 ret i32 0
564 })";
565 LLVMContext Context;
566 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
567
568 std::vector<IRInstructionData *> InstrList;
569 std::vector<unsigned> UnsignedVec;
570
571 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
572 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
573 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
574 getVectors(*M, Mapper, InstrList, UnsignedVec);
575
576 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
577 ASSERT_TRUE(UnsignedVec.size() == 3);
578 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
579 }
580
581 // Checks that stores that have the different types are mapped to
582 // different unsigned integers.
TEST(IRInstructionMapper,StoreDifferentType)583 TEST(IRInstructionMapper, StoreDifferentType) {
584 StringRef ModuleString = R"(
585 define i32 @f(i32* %a, i64* %b) {
586 bb0:
587 store i32 1, i32* %a
588 store i64 1, i64* %b
589 ret i32 0
590 })";
591 LLVMContext Context;
592 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
593
594 std::vector<IRInstructionData *> InstrList;
595 std::vector<unsigned> UnsignedVec;
596
597 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
598 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
599 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
600 getVectors(*M, Mapper, InstrList, UnsignedVec);
601
602 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
603 ASSERT_TRUE(UnsignedVec.size() == 3);
604 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
605 }
606
607 // Checks that stores that have the different aligns are mapped to different
608 // unsigned integers.
TEST(IRInstructionMapper,StoreDifferentAlign)609 TEST(IRInstructionMapper, StoreDifferentAlign) {
610 StringRef ModuleString = R"(
611 define i32 @f(i32* %a, i32* %b) {
612 bb0:
613 store i32 1, i32* %a, align 4
614 store i32 1, i32* %b, align 8
615 ret i32 0
616 })";
617 LLVMContext Context;
618 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
619
620 std::vector<IRInstructionData *> InstrList;
621 std::vector<unsigned> UnsignedVec;
622
623 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
624 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
625 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
626 getVectors(*M, Mapper, InstrList, UnsignedVec);
627
628 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
629 ASSERT_TRUE(UnsignedVec.size() == 3);
630 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
631 }
632
633 // Checks that stores that have the different volatile settings are mapped to
634 // different unsigned integers.
TEST(IRInstructionMapper,StoreDifferentVolatile)635 TEST(IRInstructionMapper, StoreDifferentVolatile) {
636 StringRef ModuleString = R"(
637 define i32 @f(i32* %a, i32* %b) {
638 bb0:
639 store volatile i32 1, i32* %a
640 store i32 1, i32* %b
641 ret i32 0
642 })";
643 LLVMContext Context;
644 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
645
646 std::vector<IRInstructionData *> InstrList;
647 std::vector<unsigned> UnsignedVec;
648
649 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
650 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
651 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
652 getVectors(*M, Mapper, InstrList, UnsignedVec);
653
654 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
655 ASSERT_TRUE(UnsignedVec.size() == 3);
656 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
657 }
658
659 // Checks that stores that have the same volatile settings are mapped to
660 // different unsigned integers.
TEST(IRInstructionMapper,StoreSameVolatile)661 TEST(IRInstructionMapper, StoreSameVolatile) {
662 StringRef ModuleString = R"(
663 define i32 @f(i32* %a, i32* %b) {
664 bb0:
665 store volatile i32 1, i32* %a
666 store volatile i32 1, i32* %b
667 ret i32 0
668 })";
669 LLVMContext Context;
670 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
671
672 std::vector<IRInstructionData *> InstrList;
673 std::vector<unsigned> UnsignedVec;
674
675 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
676 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
677 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
678 getVectors(*M, Mapper, InstrList, UnsignedVec);
679
680 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
681 ASSERT_TRUE(UnsignedVec.size() == 3);
682 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
683 }
684
685 // Checks that loads that have the same atomicity settings are mapped to
686 // different unsigned integers.
TEST(IRInstructionMapper,StoreSameAtomic)687 TEST(IRInstructionMapper, StoreSameAtomic) {
688 StringRef ModuleString = R"(
689 define i32 @f(i32* %a, i32* %b) {
690 bb0:
691 store atomic i32 1, i32* %a unordered, align 4
692 store atomic i32 1, i32* %b unordered, align 4
693 ret i32 0
694 })";
695 LLVMContext Context;
696 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
697
698 std::vector<IRInstructionData *> InstrList;
699 std::vector<unsigned> UnsignedVec;
700
701 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
702 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
703 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
704 getVectors(*M, Mapper, InstrList, UnsignedVec);
705
706 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
707 ASSERT_TRUE(UnsignedVec.size() == 3);
708 ASSERT_TRUE(UnsignedVec[0] == UnsignedVec[1]);
709 }
710
711 // Checks that loads that have the different atomicity settings are mapped to
712 // different unsigned integers.
TEST(IRInstructionMapper,StoreDifferentAtomic)713 TEST(IRInstructionMapper, StoreDifferentAtomic) {
714 StringRef ModuleString = R"(
715 define i32 @f(i32* %a, i32* %b) {
716 bb0:
717 store atomic i32 1, i32* %a unordered, align 4
718 store atomic i32 1, i32* %b monotonic, align 4
719 ret i32 0
720 })";
721 LLVMContext Context;
722 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
723
724 std::vector<IRInstructionData *> InstrList;
725 std::vector<unsigned> UnsignedVec;
726
727 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
728 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
729 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
730 getVectors(*M, Mapper, InstrList, UnsignedVec);
731
732 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
733 ASSERT_TRUE(UnsignedVec.size() == 3);
734 ASSERT_TRUE(UnsignedVec[0] != UnsignedVec[1]);
735 }
736
737 // Checks that the branch is mapped to legal when the option is set.
TEST(IRInstructionMapper,BranchLegal)738 TEST(IRInstructionMapper, BranchLegal) {
739 StringRef ModuleString = R"(
740 define i32 @f(i32 %a, i32 %b) {
741 bb0:
742 %0 = icmp slt i32 %a, %b
743 br i1 %0, label %bb0, label %bb1
744 bb1:
745 ret i32 0
746 })";
747 LLVMContext Context;
748 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
749
750 std::vector<IRInstructionData *> InstrList;
751 std::vector<unsigned> UnsignedVec;
752
753 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
754 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
755 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
756 Mapper.InstClassifier.EnableBranches = true;
757 Mapper.initializeForBBs(*M);
758 getVectors(*M, Mapper, InstrList, UnsignedVec);
759
760 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
761 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
762 ASSERT_TRUE(UnsignedVec[1] > UnsignedVec[0]);
763 ASSERT_TRUE(UnsignedVec[1] < UnsignedVec[2]);
764 }
765
766 // Checks that a PHINode is mapped to be legal.
TEST(IRInstructionMapper,PhiLegal)767 TEST(IRInstructionMapper, PhiLegal) {
768 StringRef ModuleString = R"(
769 define i32 @f(i32 %a, i32 %b) {
770 bb0:
771 %0 = phi i1 [ 0, %bb0 ], [ %0, %bb1 ]
772 %1 = add i32 %a, %b
773 ret i32 0
774 bb1:
775 ret i32 1
776 })";
777 LLVMContext Context;
778 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
779
780 std::vector<IRInstructionData *> InstrList;
781 std::vector<unsigned> UnsignedVec;
782
783 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
784 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
785 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
786 Mapper.InstClassifier.EnableBranches = true;
787 Mapper.initializeForBBs(*M);
788 getVectors(*M, Mapper, InstrList, UnsignedVec);
789
790 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
791 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
792 }
793
794 // Checks that a PHINode is mapped to be legal.
TEST(IRInstructionMapper,PhiIllegal)795 TEST(IRInstructionMapper, PhiIllegal) {
796 StringRef ModuleString = R"(
797 define i32 @f(i32 %a, i32 %b) {
798 bb0:
799 %0 = phi i1 [ 0, %bb0 ], [ %0, %bb1 ]
800 %1 = add i32 %a, %b
801 ret i32 0
802 bb1:
803 ret i32 1
804 })";
805 LLVMContext Context;
806 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
807
808 std::vector<IRInstructionData *> InstrList;
809 std::vector<unsigned> UnsignedVec;
810
811 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
812 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
813 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
814 Mapper.initializeForBBs(*M);
815 getVectors(*M, Mapper, InstrList, UnsignedVec);
816
817 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
818 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
819 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
820 }
821
822 // In most cases, the illegal instructions we are collecting don't require any
823 // sort of setup. In these cases, we can just only have illegal instructions,
824 // and the mapper will create 0 length vectors, and we can check that.
825
826 // In cases where we have legal instructions needed to set up the illegal
827 // instruction, to check illegal instructions are assigned unsigned integers
828 // from the maximum value decreasing to 0, it will be greater than a legal
829 // instruction that comes after. So to check that we have an illegal
830 // instruction, we place a legal instruction after an illegal instruction, and
831 // check that the illegal unsigned integer is greater than the unsigned integer
832 // of the legal instruction.
833
834 // Checks that an alloca instruction is mapped to be illegal.
TEST(IRInstructionMapper,AllocaIllegal)835 TEST(IRInstructionMapper, AllocaIllegal) {
836 StringRef ModuleString = R"(
837 define i32 @f(i32 %a, i32 %b) {
838 bb0:
839 %0 = alloca i32
840 ret i32 0
841 })";
842 LLVMContext Context;
843 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
844
845 std::vector<IRInstructionData *> InstrList;
846 std::vector<unsigned> UnsignedVec;
847
848 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
849 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
850 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
851 getVectors(*M, Mapper, InstrList, UnsignedVec);
852
853 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
854 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
855 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
856 }
857
858 // Checks that an getelementptr instruction is mapped to be legal. And that
859 // the operands in getelementpointer instructions are the exact same after the
860 // first element operand, which only requires the same type.
TEST(IRInstructionMapper,GetElementPtrSameEndOperands)861 TEST(IRInstructionMapper, GetElementPtrSameEndOperands) {
862 StringRef ModuleString = R"(
863 %struct.RT = type { i8, [10 x [20 x i32]], i8 }
864 %struct.ST = type { i32, double, %struct.RT }
865 define i32 @f(%struct.ST* %s, i64 %a, i64 %b) {
866 bb0:
867 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0
868 %1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %b, i32 0
869 ret i32 0
870 })";
871 LLVMContext Context;
872 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
873
874 std::vector<IRInstructionData *> InstrList;
875 std::vector<unsigned> UnsignedVec;
876
877 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
878 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
879 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
880 getVectors(*M, Mapper, InstrList, UnsignedVec);
881
882 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
883 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
884 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);
885 }
886
887 // Check that when the operands in getelementpointer instructions are not the
888 // exact same after the first element operand, the instructions are mapped to
889 // different values.
TEST(IRInstructionMapper,GetElementPtrDifferentEndOperands)890 TEST(IRInstructionMapper, GetElementPtrDifferentEndOperands) {
891 StringRef ModuleString = R"(
892 %struct.RT = type { i8, [10 x [20 x i32]], i8 }
893 %struct.ST = type { i32, double, %struct.RT }
894 define i32 @f(%struct.ST* %s, i64 %a, i64 %b) {
895 bb0:
896 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0
897 %1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %b, i32 2
898 ret i32 0
899 })";
900 LLVMContext Context;
901 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
902
903 std::vector<IRInstructionData *> InstrList;
904 std::vector<unsigned> UnsignedVec;
905
906 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
907 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
908 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
909 getVectors(*M, Mapper, InstrList, UnsignedVec);
910
911 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
912 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
913 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
914 }
915
916 // Check that when the operands in getelementpointer instructions are not the
917 // same initial base type, each instruction is mapped to a different value.
TEST(IRInstructionMapper,GetElementPtrDifferentBaseType)918 TEST(IRInstructionMapper, GetElementPtrDifferentBaseType) {
919 StringRef ModuleString = R"(
920 %struct.RT = type { i8, [10 x [20 x i32]], i8 }
921 %struct.ST = type { i32, double, %struct.RT }
922 define i32 @f(%struct.ST* %s, %struct.RT* %r, i64 %a, i64 %b) {
923 bb0:
924 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a
925 %1 = getelementptr inbounds %struct.RT, %struct.RT* %r, i64 %b
926 ret i32 0
927 })";
928 LLVMContext Context;
929 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
930
931 std::vector<IRInstructionData *> InstrList;
932 std::vector<unsigned> UnsignedVec;
933
934 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
935 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
936 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
937 getVectors(*M, Mapper, InstrList, UnsignedVec);
938
939 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
940 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
941 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
942 }
943
944 // Check that when the operands in getelementpointer instructions do not have
945 // the same inbounds modifier, they are not counted as the same.
TEST(IRInstructionMapper,GetElementPtrDifferentInBounds)946 TEST(IRInstructionMapper, GetElementPtrDifferentInBounds) {
947 StringRef ModuleString = R"(
948 %struct.RT = type { i8, [10 x [20 x i32]], i8 }
949 %struct.ST = type { i32, double, %struct.RT }
950 define i32 @f(%struct.ST* %s, %struct.RT* %r, i64 %a, i64 %b) {
951 bb0:
952 %0 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 %a, i32 0
953 %1 = getelementptr %struct.ST, %struct.ST* %s, i64 %b, i32 0
954 ret i32 0
955 })";
956 LLVMContext Context;
957 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
958
959 std::vector<IRInstructionData *> InstrList;
960 std::vector<unsigned> UnsignedVec;
961
962 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
963 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
964 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
965 getVectors(*M, Mapper, InstrList, UnsignedVec);
966
967 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
968 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
969 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
970 }
971
972 // Checks that indirect call instructions are mapped to be illegal when it is
973 // specified to disallow them.
TEST(IRInstructionMapper,CallsIllegalIndirect)974 TEST(IRInstructionMapper, CallsIllegalIndirect) {
975 StringRef ModuleString = R"(
976 define i32 @f(void()* %func) {
977 bb0:
978 call void %func()
979 ret i32 0
980 })";
981 LLVMContext Context;
982 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
983
984 std::vector<IRInstructionData *> InstrList;
985 std::vector<unsigned> UnsignedVec;
986
987 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
988 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
989 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
990 Mapper.InstClassifier.EnableIndirectCalls = false;
991 getVectors(*M, Mapper, InstrList, UnsignedVec);
992
993 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
994 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
995 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
996 }
997
998 // Checks that indirect call instructions are mapped to be legal when it is not
999 // specified to disallow them.
TEST(IRInstructionMapper,CallsLegalIndirect)1000 TEST(IRInstructionMapper, CallsLegalIndirect) {
1001 StringRef ModuleString = R"(
1002 define i32 @f(void()* %func) {
1003 bb0:
1004 call void %func()
1005 call void %func()
1006 ret i32 0
1007 })";
1008 LLVMContext Context;
1009 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1010
1011 std::vector<IRInstructionData *> InstrList;
1012 std::vector<unsigned> UnsignedVec;
1013
1014 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1015 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1016 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1017 Mapper.InstClassifier.EnableIndirectCalls = true;
1018 getVectors(*M, Mapper, InstrList, UnsignedVec);
1019
1020 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1021 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1022 }
1023
1024 // Checks that a call instruction is mapped to be legal. Here we check that
1025 // a call with the same name, and same types are mapped to the same
1026 // value.
TEST(IRInstructionMapper,CallsSameTypeSameName)1027 TEST(IRInstructionMapper, CallsSameTypeSameName) {
1028 StringRef ModuleString = R"(
1029 declare i32 @f1(i32, i32)
1030 define i32 @f(i32 %a, i32 %b) {
1031 bb0:
1032 %0 = call i32 @f1(i32 %a, i32 %b)
1033 %1 = call i32 @f1(i32 %a, i32 %b)
1034 ret i32 0
1035 })";
1036 LLVMContext Context;
1037 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1038
1039 std::vector<IRInstructionData *> InstrList;
1040 std::vector<unsigned> UnsignedVec;
1041
1042 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1043 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1044 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1045 getVectors(*M, Mapper, InstrList, UnsignedVec);
1046
1047 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1048 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1049 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);
1050 }
1051
1052 // Here we check that a calls with different names, but the same arguments types
1053 // are mapped to different value when specified that the name must match.
TEST(IRInstructionMapper,CallsSameArgTypeDifferentNameDisallowed)1054 TEST(IRInstructionMapper, CallsSameArgTypeDifferentNameDisallowed) {
1055 StringRef ModuleString = R"(
1056 declare i32 @f1(i32, i32)
1057 declare i32 @f2(i32, i32)
1058 define i32 @f(i32 %a, i32 %b) {
1059 bb0:
1060 %0 = call i32 @f1(i32 %a, i32 %b)
1061 %1 = call i32 @f2(i32 %a, i32 %b)
1062 ret i32 0
1063 })";
1064 LLVMContext Context;
1065 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1066
1067 std::vector<IRInstructionData *> InstrList;
1068 std::vector<unsigned> UnsignedVec;
1069
1070 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1071 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1072 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1073 Mapper.EnableMatchCallsByName = true;
1074 getVectors(*M, Mapper, InstrList, UnsignedVec);
1075
1076 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1077 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1078 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
1079 }
1080
1081 // Here we check that a calls with different names, but the same arguments types
1082 // are mapped to the same value when it is not specifed that they must match.
TEST(IRInstructionMapper,CallsSameArgTypeDifferentName)1083 TEST(IRInstructionMapper, CallsSameArgTypeDifferentName) {
1084 StringRef ModuleString = R"(
1085 declare i32 @f1(i32, i32)
1086 declare i32 @f2(i32, i32)
1087 define i32 @f(i32 %a, i32 %b) {
1088 bb0:
1089 %0 = call i32 @f1(i32 %a, i32 %b)
1090 %1 = call i32 @f2(i32 %a, i32 %b)
1091 ret i32 0
1092 })";
1093 LLVMContext Context;
1094 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1095
1096 std::vector<IRInstructionData *> InstrList;
1097 std::vector<unsigned> UnsignedVec;
1098
1099 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1100 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1101 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1102 Mapper.EnableMatchCallsByName = false;
1103 getVectors(*M, Mapper, InstrList, UnsignedVec);
1104
1105 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1106 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1107 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);
1108 }
1109
1110 // Here we check that a calls with different names, and different arguments
1111 // types are mapped to different value.
TEST(IRInstructionMapper,CallsDifferentArgTypeDifferentName)1112 TEST(IRInstructionMapper, CallsDifferentArgTypeDifferentName) {
1113 StringRef ModuleString = R"(
1114 declare i32 @f1(i32, i32)
1115 declare i32 @f2(i32)
1116 define i32 @f(i32 %a, i32 %b) {
1117 bb0:
1118 %0 = call i32 @f1(i32 %a, i32 %b)
1119 %1 = call i32 @f2(i32 %a)
1120 ret i32 0
1121 })";
1122 LLVMContext Context;
1123 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1124
1125 std::vector<IRInstructionData *> InstrList;
1126 std::vector<unsigned> UnsignedVec;
1127
1128 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1129 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1130 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1131 getVectors(*M, Mapper, InstrList, UnsignedVec);
1132
1133 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1134 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1135 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
1136 }
1137
1138 // Here we check that calls with different names, and different return
1139 // types are mapped to different value.
TEST(IRInstructionMapper,CallsDifferentReturnTypeDifferentName)1140 TEST(IRInstructionMapper, CallsDifferentReturnTypeDifferentName) {
1141 StringRef ModuleString = R"(
1142 declare i64 @f1(i32, i32)
1143 declare i32 @f2(i32, i32)
1144 define i32 @f(i32 %a, i32 %b) {
1145 bb0:
1146 %0 = call i64 @f1(i32 %a, i32 %b)
1147 %1 = call i32 @f2(i32 %a, i32 %b)
1148 ret i32 0
1149 })";
1150 LLVMContext Context;
1151 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1152
1153 std::vector<IRInstructionData *> InstrList;
1154 std::vector<unsigned> UnsignedVec;
1155
1156 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1157 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1158 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1159 getVectors(*M, Mapper, InstrList, UnsignedVec);
1160
1161 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1162 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1163 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
1164 }
1165
1166 // Here we check that calls with the same name, types, and parameters map to the
1167 // same unsigned integer.
TEST(IRInstructionMapper,CallsSameParameters)1168 TEST(IRInstructionMapper, CallsSameParameters) {
1169 StringRef ModuleString = R"(
1170 declare i32 @f1(i32, i32)
1171 define i32 @f(i32 %a, i32 %b) {
1172 bb0:
1173 %0 = tail call fastcc i32 @f1(i32 %a, i32 %b)
1174 %1 = tail call fastcc i32 @f1(i32 %a, i32 %b)
1175 ret i32 0
1176 })";
1177 LLVMContext Context;
1178 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1179
1180 std::vector<IRInstructionData *> InstrList;
1181 std::vector<unsigned> UnsignedVec;
1182
1183 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1184 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1185 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1186 getVectors(*M, Mapper, InstrList, UnsignedVec);
1187
1188 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1189 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1190 ASSERT_EQ(UnsignedVec[0], UnsignedVec[1]);
1191 }
1192
1193 // Here we check that calls with different tail call settings are mapped to
1194 // different values.
TEST(IRInstructionMapper,CallsDifferentTails)1195 TEST(IRInstructionMapper, CallsDifferentTails) {
1196 StringRef ModuleString = R"(
1197 declare i32 @f1(i32, i32)
1198 define i32 @f(i32 %a, i32 %b) {
1199 bb0:
1200 %0 = tail call i32 @f1(i32 %a, i32 %b)
1201 %1 = call i32 @f1(i32 %a, i32 %b)
1202 ret i32 0
1203 })";
1204 LLVMContext Context;
1205 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1206
1207 std::vector<IRInstructionData *> InstrList;
1208 std::vector<unsigned> UnsignedVec;
1209
1210 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1211 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1212 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1213 getVectors(*M, Mapper, InstrList, UnsignedVec);
1214
1215 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1216 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1217 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
1218 }
1219
1220 // Here we check that calls with different calling convention settings are
1221 // mapped to different values.
TEST(IRInstructionMapper,CallsDifferentCallingConventions)1222 TEST(IRInstructionMapper, CallsDifferentCallingConventions) {
1223 StringRef ModuleString = R"(
1224 declare i32 @f1(i32, i32)
1225 define i32 @f(i32 %a, i32 %b) {
1226 bb0:
1227 %0 = call fastcc i32 @f1(i32 %a, i32 %b)
1228 %1 = call i32 @f1(i32 %a, i32 %b)
1229 ret i32 0
1230 })";
1231 LLVMContext Context;
1232 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1233
1234 std::vector<IRInstructionData *> InstrList;
1235 std::vector<unsigned> UnsignedVec;
1236
1237 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1238 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1239 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1240 getVectors(*M, Mapper, InstrList, UnsignedVec);
1241
1242 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1243 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1244 ASSERT_NE(UnsignedVec[0], UnsignedVec[1]);
1245 }
1246
1247 // Checks that an invoke instruction is mapped to be illegal. Invoke
1248 // instructions are considered to be illegal because of the change in the
1249 // control flow that is currently not recognized.
TEST(IRInstructionMapper,InvokeIllegal)1250 TEST(IRInstructionMapper, InvokeIllegal) {
1251 StringRef ModuleString = R"(
1252 define i32 @f(i8 *%gep1, i32 %b) {
1253 then:
1254 invoke i32 undef(i8* undef)
1255 to label %invoke unwind label %lpad
1256
1257 invoke:
1258 unreachable
1259
1260 lpad:
1261 landingpad { i8*, i32 }
1262 catch i8* null
1263 unreachable
1264 })";
1265 LLVMContext Context;
1266 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1267
1268 std::vector<IRInstructionData *> InstrList;
1269 std::vector<unsigned> UnsignedVec;
1270
1271 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1272 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1273 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1274 getVectors(*M, Mapper, InstrList, UnsignedVec);
1275
1276 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1277 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1278 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1279 }
1280
1281 // Checks that an callbr instructions are considered to be illegal. Callbr
1282 // instructions are considered to be illegal because of the change in the
1283 // control flow that is currently not recognized.
TEST(IRInstructionMapper,CallBrInstIllegal)1284 TEST(IRInstructionMapper, CallBrInstIllegal) {
1285 StringRef ModuleString = R"(
1286 define void @test() {
1287 fail:
1288 ret void
1289 }
1290
1291 define i32 @f(i32 %a, i32 %b) {
1292 bb0:
1293 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]
1294 fail:
1295 ret i32 0
1296 normal:
1297 ret i32 0
1298 })";
1299 LLVMContext Context;
1300 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1301
1302 std::vector<IRInstructionData *> InstrList;
1303 std::vector<unsigned> UnsignedVec;
1304
1305 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1306 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1307 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1308 getVectors(*M, Mapper, InstrList, UnsignedVec);
1309
1310 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1311 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1312 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1313 }
1314
1315 // Checks that an debuginfo records are mapped to be invisible. Since they
1316 // do not semantically change the program, they can be recognized as similar.
TEST(IRInstructionMapper,DebugInfoInvisible)1317 TEST(IRInstructionMapper, DebugInfoInvisible) {
1318 StringRef ModuleString = R"(
1319 define i32 @f(i32 %a, i32 %b) {
1320 then:
1321 %0 = add i32 %a, %b
1322 #dbg_value(i32 0, !0, !0, !0)
1323 %1 = add i32 %a, %b
1324 ret i32 0
1325 }
1326
1327 !0 = distinct !{!"test\00", i32 10})";
1328 LLVMContext Context;
1329 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1330
1331 std::vector<IRInstructionData *> InstrList;
1332 std::vector<unsigned> UnsignedVec;
1333
1334 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1335 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1336 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1337 getVectors(*M, Mapper, InstrList, UnsignedVec);
1338
1339 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1340 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(3));
1341 }
1342
1343 // The following are all exception handling intrinsics. We do not currently
1344 // handle these instruction because they are very context dependent.
1345
1346 // Checks that an eh.typeid.for intrinsic is mapped to be illegal.
TEST(IRInstructionMapper,ExceptionHandlingTypeIdIllegal)1347 TEST(IRInstructionMapper, ExceptionHandlingTypeIdIllegal) {
1348 StringRef ModuleString = R"(
1349 @_ZTIi = external constant i8*
1350 define i32 @f() {
1351 then:
1352 %0 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
1353 ret i32 0
1354 }
1355
1356 declare i32 @llvm.eh.typeid.for(i8*))";
1357 LLVMContext Context;
1358 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1359
1360 std::vector<IRInstructionData *> InstrList;
1361 std::vector<unsigned> UnsignedVec;
1362
1363 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1364 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1365 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1366 getVectors(*M, Mapper, InstrList, UnsignedVec);
1367
1368 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1369 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1370 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1371 }
1372
1373 // Checks that an eh.exceptioncode intrinsic is mapped to be illegal.
TEST(IRInstructionMapper,ExceptionHandlingExceptionCodeIllegal)1374 TEST(IRInstructionMapper, ExceptionHandlingExceptionCodeIllegal) {
1375 StringRef ModuleString = R"(
1376 define i32 @f(i32 %a, i32 %b) {
1377 entry:
1378 %0 = catchswitch within none [label %__except] unwind to caller
1379
1380 __except:
1381 %1 = catchpad within %0 [i8* null]
1382 catchret from %1 to label %__except
1383
1384 then:
1385 %2 = call i32 @llvm.eh.exceptioncode(token %1)
1386 ret i32 0
1387 }
1388
1389 declare i32 @llvm.eh.exceptioncode(token))";
1390 LLVMContext Context;
1391 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1392
1393 std::vector<IRInstructionData *> InstrList;
1394 std::vector<unsigned> UnsignedVec;
1395
1396 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1397 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1398 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1399 getVectors(*M, Mapper, InstrList, UnsignedVec);
1400
1401 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1402 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1403 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1404 }
1405
1406 // Checks that an eh.unwind intrinsic is mapped to be illegal.
TEST(IRInstructionMapper,ExceptionHandlingUnwindIllegal)1407 TEST(IRInstructionMapper, ExceptionHandlingUnwindIllegal) {
1408 StringRef ModuleString = R"(
1409 define i32 @f(i32 %a, i32 %b) {
1410 entry:
1411 call void @llvm.eh.unwind.init()
1412 ret i32 0
1413 }
1414
1415 declare void @llvm.eh.unwind.init())";
1416 LLVMContext Context;
1417 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1418
1419 std::vector<IRInstructionData *> InstrList;
1420 std::vector<unsigned> UnsignedVec;
1421
1422 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1423 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1424 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1425 getVectors(*M, Mapper, InstrList, UnsignedVec);
1426
1427 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1428 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1429 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1430 }
1431
1432 // Checks that an eh.exceptionpointer intrinsic is mapped to be illegal.
TEST(IRInstructionMapper,ExceptionHandlingExceptionPointerIllegal)1433 TEST(IRInstructionMapper, ExceptionHandlingExceptionPointerIllegal) {
1434 StringRef ModuleString = R"(
1435 define i32 @f(i32 %a, i32 %b) {
1436 entry:
1437 %0 = call i8* @llvm.eh.exceptionpointer.p0i8(i32 0)
1438 ret i32 0
1439 }
1440
1441 declare i8* @llvm.eh.exceptionpointer.p0i8(i32))";
1442 LLVMContext Context;
1443 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1444
1445 std::vector<IRInstructionData *> InstrList;
1446 std::vector<unsigned> UnsignedVec;
1447
1448 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1449 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1450 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1451 getVectors(*M, Mapper, InstrList, UnsignedVec);
1452
1453 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1454 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1455 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1456 }
1457
1458 // Checks that a catchpad instruction is mapped to an illegal value.
TEST(IRInstructionMapper,CatchpadIllegal)1459 TEST(IRInstructionMapper, CatchpadIllegal) {
1460 StringRef ModuleString = R"(
1461 declare void @llvm.donothing() nounwind readnone
1462
1463 define void @function() personality i8 3 {
1464 entry:
1465 invoke void @llvm.donothing() to label %normal unwind label %exception
1466 exception:
1467 %cs1 = catchswitch within none [label %catchpad1] unwind to caller
1468 catchpad1:
1469 catchpad within %cs1 []
1470 br label %normal
1471 normal:
1472 ret void
1473 })";
1474 LLVMContext Context;
1475 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1476
1477 std::vector<IRInstructionData *> InstrList;
1478 std::vector<unsigned> UnsignedVec;
1479
1480 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1481 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1482 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1483 getVectors(*M, Mapper, InstrList, UnsignedVec);
1484
1485 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1486 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1487 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1488 }
1489
1490 // Checks that a cleanuppad instruction is mapped to an illegal value.
TEST(IRInstructionMapper,CleanuppadIllegal)1491 TEST(IRInstructionMapper, CleanuppadIllegal) {
1492 StringRef ModuleString = R"(
1493 declare void @llvm.donothing() nounwind readnone
1494
1495 define void @function() personality i8 3 {
1496 entry:
1497 invoke void @llvm.donothing() to label %normal unwind label %exception
1498 exception:
1499 %cs1 = catchswitch within none [label %catchpad1] unwind to caller
1500 catchpad1:
1501 %clean = cleanuppad within none []
1502 br label %normal
1503 normal:
1504 ret void
1505 })";
1506 LLVMContext Context;
1507 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1508
1509 std::vector<IRInstructionData *> InstrList;
1510 std::vector<unsigned> UnsignedVec;
1511
1512 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1513 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1514 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1515 getVectors(*M, Mapper, InstrList, UnsignedVec);
1516
1517 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1518 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(1));
1519 ASSERT_GT(UnsignedVec[0], Mapper.IllegalInstrNumber);
1520 }
1521
1522 // The following three instructions are memory transfer and setting based, which
1523 // are considered illegal since is extra checking needed to handle the address
1524 // space checking.
1525
1526 // Checks that a memset instruction is mapped to an illegal value when
1527 // specified.
TEST(IRInstructionMapper,MemSetIllegal)1528 TEST(IRInstructionMapper, MemSetIllegal) {
1529 StringRef ModuleString = R"(
1530 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
1531
1532 define i64 @function(i64 %x, i64 %z, i64 %n) {
1533 entry:
1534 %pool = alloca [59 x i64], align 4
1535 %tmp = bitcast [59 x i64]* %pool to i8*
1536 call void @llvm.memset.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
1537 %cmp3 = icmp eq i64 %n, 0
1538 %a = add i64 %x, %z
1539 %c = add i64 %x, %z
1540 ret i64 0
1541 })";
1542 LLVMContext Context;
1543 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1544
1545 std::vector<IRInstructionData *> InstrList;
1546 std::vector<unsigned> UnsignedVec;
1547
1548 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1549 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1550 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1551 Mapper.InstClassifier.EnableIntrinsics = false;
1552 getVectors(*M, Mapper, InstrList, UnsignedVec);
1553
1554 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1555 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));
1556 ASSERT_TRUE(UnsignedVec[2] < UnsignedVec[0]);
1557 }
1558
1559 // Checks that a memcpy instruction is mapped to an illegal value when
1560 // specified.
TEST(IRInstructionMapper,MemCpyIllegal)1561 TEST(IRInstructionMapper, MemCpyIllegal) {
1562 StringRef ModuleString = R"(
1563 declare void @llvm.memcpy.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
1564
1565 define i64 @function(i64 %x, i64 %z, i64 %n) {
1566 entry:
1567 %pool = alloca [59 x i64], align 4
1568 %tmp = bitcast [59 x i64]* %pool to i8*
1569 call void @llvm.memcpy.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
1570 %cmp3 = icmp eq i64 %n, 0
1571 %a = add i64 %x, %z
1572 %c = add i64 %x, %z
1573 ret i64 0
1574 })";
1575 LLVMContext Context;
1576 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1577
1578 std::vector<IRInstructionData *> InstrList;
1579 std::vector<unsigned> UnsignedVec;
1580
1581 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1582 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1583 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1584 Mapper.InstClassifier.EnableIntrinsics = false;
1585 getVectors(*M, Mapper, InstrList, UnsignedVec);
1586
1587 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1588 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));
1589 ASSERT_GT(UnsignedVec[2], UnsignedVec[3]);
1590 ASSERT_LT(UnsignedVec[2], UnsignedVec[0]);
1591 }
1592
1593 // Checks that a memmove instruction is mapped to an illegal value when
1594 // specified.
TEST(IRInstructionMapper,MemMoveIllegal)1595 TEST(IRInstructionMapper, MemMoveIllegal) {
1596 StringRef ModuleString = R"(
1597 declare void @llvm.memmove.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
1598
1599 define i64 @function(i64 %x, i64 %z, i64 %n) {
1600 entry:
1601 %pool = alloca [59 x i64], align 4
1602 %tmp = bitcast [59 x i64]* %pool to i8*
1603 call void @llvm.memmove.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
1604 %cmp3 = icmp eq i64 %n, 0
1605 %a = add i64 %x, %z
1606 %c = add i64 %x, %z
1607 ret i64 0
1608 })";
1609 LLVMContext Context;
1610 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1611
1612 std::vector<IRInstructionData *> InstrList;
1613 std::vector<unsigned> UnsignedVec;
1614
1615 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1616 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1617 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1618 Mapper.InstClassifier.EnableIntrinsics = false;
1619 getVectors(*M, Mapper, InstrList, UnsignedVec);
1620
1621 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1622 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(7));
1623 ASSERT_LT(UnsignedVec[2], UnsignedVec[0]);
1624 }
1625
1626 // Checks that mem* instructions are mapped to an legal value when not
1627 // specified, and that all the intrinsics are marked differently.
TEST(IRInstructionMapper,MemOpsLegal)1628 TEST(IRInstructionMapper, MemOpsLegal) {
1629 StringRef ModuleString = R"(
1630 declare void @llvm.memmove.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
1631 declare void @llvm.memcpy.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
1632 declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i32, i1)
1633
1634 define i64 @function(i64 %x, i64 %z, i64 %n) {
1635 entry:
1636 %pool = alloca [59 x i64], align 4
1637 %tmp = bitcast [59 x i64]* %pool to i8*
1638 call void @llvm.memmove.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
1639 call void @llvm.memcpy.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
1640 call void @llvm.memset.p0i8.i64(i8* nonnull %tmp, i8 0, i64 236, i32 4, i1 false)
1641 %cmp3 = icmp eq i64 %n, 0
1642 %a = add i64 %x, %z
1643 %c = add i64 %x, %z
1644 ret i64 0
1645 })";
1646 LLVMContext Context;
1647 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1648
1649 std::vector<IRInstructionData *> InstrList;
1650 std::vector<unsigned> UnsignedVec;
1651
1652 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1653 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1654 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1655 Mapper.InstClassifier.EnableIntrinsics = true;
1656 getVectors(*M, Mapper, InstrList, UnsignedVec);
1657
1658 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1659 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(9));
1660 ASSERT_LT(UnsignedVec[2], UnsignedVec[3]);
1661 ASSERT_LT(UnsignedVec[3], UnsignedVec[4]);
1662 ASSERT_LT(UnsignedVec[4], UnsignedVec[5]);
1663 }
1664
1665 // Checks that a variable argument instructions are mapped to an illegal value.
1666 // We exclude variable argument instructions since variable arguments
1667 // requires extra checking of the argument list.
TEST(IRInstructionMapper,VarArgsIllegal)1668 TEST(IRInstructionMapper, VarArgsIllegal) {
1669 StringRef ModuleString = R"(
1670 declare void @llvm.va_start(i8*)
1671 declare void @llvm.va_copy(i8*, i8*)
1672 declare void @llvm.va_end(i8*)
1673
1674 define i32 @func1(i32 %a, double %b, i8* %v, ...) nounwind {
1675 entry:
1676 %a.addr = alloca i32, align 4
1677 %b.addr = alloca double, align 8
1678 %ap = alloca i8*, align 4
1679 %c = alloca i32, align 4
1680 store i32 %a, i32* %a.addr, align 4
1681 store double %b, double* %b.addr, align 8
1682 %ap1 = bitcast i8** %ap to i8*
1683 call void @llvm.va_start(i8* %ap1)
1684 store double %b, double* %b.addr, align 8
1685 store double %b, double* %b.addr, align 8
1686 %0 = va_arg i8** %ap, i32
1687 store double %b, double* %b.addr, align 8
1688 store double %b, double* %b.addr, align 8
1689 call void @llvm.va_copy(i8* %v, i8* %ap1)
1690 store double %b, double* %b.addr, align 8
1691 store double %b, double* %b.addr, align 8
1692 call void @llvm.va_end(i8* %ap1)
1693 store i32 %0, i32* %c, align 4
1694 %tmp = load i32, i32* %c, align 4
1695 ret i32 %tmp
1696 })";
1697 LLVMContext Context;
1698 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1699
1700 std::vector<IRInstructionData *> InstrList;
1701 std::vector<unsigned> UnsignedVec;
1702
1703 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1704 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1705 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1706 Mapper.InstClassifier.EnableIntrinsics = false;
1707 getVectors(*M, Mapper, InstrList, UnsignedVec);
1708
1709 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
1710 ASSERT_EQ(UnsignedVec.size(), static_cast<unsigned>(17));
1711 ASSERT_TRUE(UnsignedVec[7] < UnsignedVec[0]);
1712 ASSERT_TRUE(UnsignedVec[13] < UnsignedVec[10]);
1713 ASSERT_TRUE(UnsignedVec[16] < UnsignedVec[13]);
1714 }
1715
1716 // Check the length of adding two illegal instructions one after th other. We
1717 // should find that only one element is added for each illegal range.
TEST(IRInstructionMapper,RepeatedIllegalLength)1718 TEST(IRInstructionMapper, RepeatedIllegalLength) {
1719 StringRef ModuleString = R"(
1720 define i32 @f(i32 %a, i32 %b) {
1721 bb0:
1722 %0 = add i32 %a, %b
1723 %1 = mul i32 %a, %b
1724 %2 = alloca i32
1725 %3 = alloca i32
1726 %4 = add i32 %a, %b
1727 %5 = mul i32 %a, %b
1728 ret i32 0
1729 })";
1730 LLVMContext Context;
1731 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1732
1733 std::vector<IRInstructionData *> InstrList;
1734 std::vector<unsigned> UnsignedVec;
1735
1736 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1737 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1738 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1739 getVectors(*M, Mapper, InstrList, UnsignedVec);
1740
1741 // Check that the size of the unsigned vector and the instruction list are the
1742 // same as a safety check.
1743 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1744
1745 // Make sure that the unsigned vector is the expected size.
1746 ASSERT_TRUE(UnsignedVec.size() == 6);
1747 }
1748
1749 // A helper function that accepts an instruction list from a module made up of
1750 // two blocks of two legal instructions and terminator, and checks them for
1751 // instruction similarity.
longSimCandCompare(std::vector<IRInstructionData * > & InstrList,bool Structure=false,unsigned Length=2,unsigned StartIdxOne=0,unsigned StartIdxTwo=3)1752 static bool longSimCandCompare(std::vector<IRInstructionData *> &InstrList,
1753 bool Structure = false, unsigned Length = 2,
1754 unsigned StartIdxOne = 0,
1755 unsigned StartIdxTwo = 3) {
1756 std::vector<IRInstructionData *>::iterator Start, End;
1757
1758 Start = InstrList.begin();
1759 End = InstrList.begin();
1760
1761 std::advance(End, StartIdxOne + Length - 1);
1762 IRSimilarityCandidate Cand1(StartIdxOne, Length, *Start, *End);
1763
1764 Start = InstrList.begin();
1765 End = InstrList.begin();
1766
1767 std::advance(Start, StartIdxTwo);
1768 std::advance(End, StartIdxTwo + Length - 1);
1769 IRSimilarityCandidate Cand2(StartIdxTwo, Length, *Start, *End);
1770 if (Structure)
1771 return IRSimilarityCandidate::compareStructure(Cand1, Cand2);
1772 return IRSimilarityCandidate::isSimilar(Cand1, Cand2);
1773 }
1774
1775 // Checks that two adds with commuted operands are considered to be the same
1776 // instructions.
TEST(IRSimilarityCandidate,CheckIdenticalInstructions)1777 TEST(IRSimilarityCandidate, CheckIdenticalInstructions) {
1778 StringRef ModuleString = R"(
1779 define i32 @f(i32 %a, i32 %b) {
1780 bb0:
1781 %0 = add i32 %a, %b
1782 %1 = add i32 %b, %a
1783 ret i32 0
1784 })";
1785 LLVMContext Context;
1786 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1787
1788 std::vector<IRInstructionData *> InstrList;
1789 std::vector<unsigned> UnsignedVec;
1790
1791 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1792 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1793 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1794 getVectors(*M, Mapper, InstrList, UnsignedVec);
1795
1796 // Check to make sure that we have a long enough region.
1797 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(3));
1798 // Check that the instructions were added correctly to both vectors.
1799 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1800
1801 std::vector<IRInstructionData *>::iterator Start, End;
1802 Start = InstrList.begin();
1803 End = InstrList.begin();
1804 std::advance(End, 1);
1805 IRSimilarityCandidate Cand1(0, 2, *Start, *End);
1806 IRSimilarityCandidate Cand2(0, 2, *Start, *End);
1807
1808 ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
1809 }
1810
1811 // Checks that comparison instructions are found to be similar instructions
1812 // when the operands are flipped and the predicate is also swapped.
TEST(IRSimilarityCandidate,PredicateIsomorphism)1813 TEST(IRSimilarityCandidate, PredicateIsomorphism) {
1814 StringRef ModuleString = R"(
1815 define i32 @f(i32 %a, i32 %b) {
1816 bb0:
1817 %0 = icmp sgt i32 %a, %b
1818 %1 = add i32 %b, %a
1819 br label %bb1
1820 bb1:
1821 %2 = icmp slt i32 %a, %b
1822 %3 = add i32 %a, %b
1823 ret i32 0
1824 })";
1825 LLVMContext Context;
1826 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1827
1828 std::vector<IRInstructionData *> InstrList;
1829 std::vector<unsigned> UnsignedVec;
1830
1831 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1832 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1833 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1834 getVectors(*M, Mapper, InstrList, UnsignedVec);
1835
1836 ASSERT_TRUE(InstrList.size() > 5);
1837 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1838
1839 std::vector<IRInstructionData *>::iterator Start, End;
1840 Start = InstrList.begin();
1841 End = InstrList.begin();
1842
1843 std::advance(End, 1);
1844 IRSimilarityCandidate Cand1(0, 2, *Start, *End);
1845
1846 Start = InstrList.begin();
1847 End = InstrList.begin();
1848
1849 std::advance(Start, 3);
1850 std::advance(End, 4);
1851 IRSimilarityCandidate Cand2(3, 2, *Start, *End);
1852
1853 ASSERT_TRUE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
1854 }
1855
1856 // Checks that IRSimilarityCandidates wrapping these two regions of instructions
1857 // are able to differentiate between instructions that have different opcodes.
TEST(IRSimilarityCandidate,CheckRegionsDifferentInstruction)1858 TEST(IRSimilarityCandidate, CheckRegionsDifferentInstruction) {
1859 StringRef ModuleString = R"(
1860 define i32 @f(i32 %a, i32 %b) {
1861 bb0:
1862 %0 = add i32 %a, %b
1863 %1 = add i32 %b, %a
1864 ret i32 0
1865 bb1:
1866 %2 = sub i32 %a, %b
1867 %3 = add i32 %b, %a
1868 ret i32 0
1869 })";
1870 LLVMContext Context;
1871 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1872
1873 std::vector<IRInstructionData *> InstrList;
1874 std::vector<unsigned> UnsignedVec;
1875
1876 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1877 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1878 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1879 getVectors(*M, Mapper, InstrList, UnsignedVec);
1880
1881 // Check to make sure that we have a long enough region.
1882 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
1883 // Check that the instructions were added correctly to both vectors.
1884 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1885
1886 ASSERT_FALSE(longSimCandCompare(InstrList));
1887 }
1888
1889 // Checks that IRSimilarityCandidates wrapping these two regions of instructions
1890 // are able to differentiate between instructions that have different types.
TEST(IRSimilarityCandidate,CheckRegionsDifferentTypes)1891 TEST(IRSimilarityCandidate, CheckRegionsDifferentTypes) {
1892 StringRef ModuleString = R"(
1893 define i32 @f(i32 %a, i32 %b, i64 %c, i64 %d) {
1894 bb0:
1895 %0 = add i32 %a, %b
1896 %1 = add i32 %b, %a
1897 ret i32 0
1898 bb1:
1899 %2 = add i64 %c, %d
1900 %3 = add i64 %d, %c
1901 ret i32 0
1902 })";
1903 LLVMContext Context;
1904 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1905
1906 std::vector<IRInstructionData *> InstrList;
1907 std::vector<unsigned> UnsignedVec;
1908
1909 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1910 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1911 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1912 getVectors(*M, Mapper, InstrList, UnsignedVec);
1913
1914 // Check to make sure that we have a long enough region.
1915 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
1916 // Check that the instructions were added correctly to both vectors.
1917 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1918
1919 ASSERT_FALSE(longSimCandCompare(InstrList));
1920 }
1921
1922 // Check that debug records do not impact similarity. They are marked as
1923 // invisible.
TEST(IRSimilarityCandidate,IdenticalWithDebug)1924 TEST(IRSimilarityCandidate, IdenticalWithDebug) {
1925 StringRef ModuleString = R"(
1926 define i32 @f(i32 %a, i32 %b) {
1927 bb0:
1928 %0 = add i32 %a, %b
1929 #dbg_value(i32 0, !0, !0, !0)
1930 %1 = add i32 %b, %a
1931 ret i32 0
1932 bb1:
1933 %2 = add i32 %a, %b
1934 #dbg_value(i32 1, !1, !1, !1)
1935 %3 = add i32 %b, %a
1936 ret i32 0
1937 bb2:
1938 %4 = add i32 %a, %b
1939 %5 = add i32 %b, %a
1940 ret i32 0
1941 }
1942
1943 !0 = distinct !{!"test\00", i32 10}
1944 !1 = distinct !{!"test\00", i32 11})";
1945 LLVMContext Context;
1946 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1947
1948 std::vector<IRInstructionData *> InstrList;
1949 std::vector<unsigned> UnsignedVec;
1950
1951 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1952 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1953 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1954 getVectors(*M, Mapper, InstrList, UnsignedVec);
1955
1956 // Check to make sure that we have a long enough region.
1957 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(9));
1958 // Check that the instructions were added correctly to both vectors.
1959 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1960
1961 ASSERT_TRUE(longSimCandCompare(InstrList));
1962 }
1963
1964 // Checks that IRSimilarityCandidates that include illegal instructions, are not
1965 // considered to be the same set of instructions. In these sets of instructions
1966 // the allocas are illegal.
TEST(IRSimilarityCandidate,IllegalInCandidate)1967 TEST(IRSimilarityCandidate, IllegalInCandidate) {
1968 StringRef ModuleString = R"(
1969 define i32 @f(i32 %a, i32 %b) {
1970 bb0:
1971 %0 = add i32 %a, %b
1972 %1 = add i32 %a, %b
1973 %2 = alloca i32
1974 ret i32 0
1975 bb1:
1976 %3 = add i32 %a, %b
1977 %4 = add i32 %a, %b
1978 %5 = alloca i32
1979 ret i32 0
1980 })";
1981 LLVMContext Context;
1982 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
1983
1984 std::vector<IRInstructionData *> InstrList;
1985 std::vector<unsigned> UnsignedVec;
1986
1987 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
1988 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
1989 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
1990 getVectors(*M, Mapper, InstrList, UnsignedVec);
1991
1992 // Check to make sure that we have a long enough region.
1993 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
1994 // Check that the instructions were added correctly to both vectors.
1995 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
1996
1997 std::vector<IRInstructionData *>::iterator Start, End;
1998
1999 Start = InstrList.begin();
2000 End = InstrList.begin();
2001
2002 std::advance(End, 2);
2003 IRSimilarityCandidate Cand1(0, 3, *Start, *End);
2004
2005 Start = InstrList.begin();
2006 End = InstrList.begin();
2007
2008 std::advance(Start, 3);
2009 std::advance(End, 5);
2010 IRSimilarityCandidate Cand2(3, 3, *Start, *End);
2011 ASSERT_FALSE(IRSimilarityCandidate::isSimilar(Cand1, Cand2));
2012 }
2013
2014 // Checks that different structure, in this case, where we introduce a new
2015 // needed input in one region, is recognized as different.
TEST(IRSimilarityCandidate,DifferentStructure)2016 TEST(IRSimilarityCandidate, DifferentStructure) {
2017 StringRef ModuleString = R"(
2018 define i32 @f(i32 %a, i32 %b) {
2019 bb0:
2020 %0 = add i32 %a, %b
2021 %1 = add i32 %b, %a
2022 ret i32 0
2023 bb1:
2024 %2 = add i32 %a, %b
2025 %3 = add i32 %b, %0
2026 ret i32 0
2027 })";
2028 LLVMContext Context;
2029 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2030
2031 std::vector<IRInstructionData *> InstrList;
2032 std::vector<unsigned> UnsignedVec;
2033
2034 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2035 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2036 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2037 getVectors(*M, Mapper, InstrList, UnsignedVec);
2038
2039 // Check to make sure that we have a long enough region.
2040 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
2041 // Check that the instructions were added correctly to both vectors.
2042 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2043
2044 ASSERT_FALSE(longSimCandCompare(InstrList, true));
2045 }
2046
2047 // Checks that comparison instructions are found to have the same structure
2048 // when the operands are flipped and the predicate is also swapped.
TEST(IRSimilarityCandidate,PredicateIsomorphismStructure)2049 TEST(IRSimilarityCandidate, PredicateIsomorphismStructure) {
2050 StringRef ModuleString = R"(
2051 define i32 @f(i32 %a, i32 %b) {
2052 bb0:
2053 %0 = icmp sgt i32 %a, %b
2054 %1 = add i32 %a, %b
2055 br label %bb1
2056 bb1:
2057 %2 = icmp slt i32 %b, %a
2058 %3 = add i32 %a, %b
2059 ret i32 0
2060 })";
2061 LLVMContext Context;
2062 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2063
2064 std::vector<IRInstructionData *> InstrList;
2065 std::vector<unsigned> UnsignedVec;
2066
2067 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2068 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2069 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2070 getVectors(*M, Mapper, InstrList, UnsignedVec);
2071
2072 ASSERT_TRUE(InstrList.size() > 5);
2073 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2074
2075 ASSERT_TRUE(longSimCandCompare(InstrList, true));
2076 }
2077
2078 // Checks that different predicates are counted as diferent.
TEST(IRSimilarityCandidate,PredicateDifference)2079 TEST(IRSimilarityCandidate, PredicateDifference) {
2080 StringRef ModuleString = R"(
2081 define i32 @f(i32 %a, i32 %b) {
2082 bb0:
2083 %0 = icmp sge i32 %a, %b
2084 %1 = add i32 %b, %a
2085 br label %bb1
2086 bb1:
2087 %2 = icmp slt i32 %b, %a
2088 %3 = add i32 %a, %b
2089 ret i32 0
2090 })";
2091 LLVMContext Context;
2092 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2093
2094 std::vector<IRInstructionData *> InstrList;
2095 std::vector<unsigned> UnsignedVec;
2096
2097 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2098 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2099 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2100 getVectors(*M, Mapper, InstrList, UnsignedVec);
2101
2102 ASSERT_TRUE(InstrList.size() > 5);
2103 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2104
2105 ASSERT_FALSE(longSimCandCompare(InstrList));
2106 }
2107
2108 // Checks that the same structure is recognized between two candidates. The
2109 // items %a and %b are used in the same way in both sets of instructions.
TEST(IRSimilarityCandidate,SameStructure)2110 TEST(IRSimilarityCandidate, SameStructure) {
2111 StringRef ModuleString = R"(
2112 define i32 @f(i32 %a, i32 %b) {
2113 bb0:
2114 %0 = add i32 %a, %b
2115 %1 = sub i32 %b, %a
2116 ret i32 0
2117 bb1:
2118 %2 = add i32 %a, %b
2119 %3 = sub i32 %b, %a
2120 ret i32 0
2121 })";
2122 LLVMContext Context;
2123 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2124
2125 std::vector<IRInstructionData *> InstrList;
2126 std::vector<unsigned> UnsignedVec;
2127
2128 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2129 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2130 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2131 getVectors(*M, Mapper, InstrList, UnsignedVec);
2132
2133 // Check to make sure that we have a long enough region.
2134 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
2135 // Check that the instructions were added correctly to both vectors.
2136 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2137
2138 ASSERT_TRUE(longSimCandCompare(InstrList, true));
2139 }
2140
2141 // Checks that the canonical numbering between two candidates matches the found
2142 // mapping between two candidates.
TEST(IRSimilarityCandidate,CanonicalNumbering)2143 TEST(IRSimilarityCandidate, CanonicalNumbering) {
2144 StringRef ModuleString = R"(
2145 define i32 @f(i32 %a, i32 %b) {
2146 bb0:
2147 %0 = add i32 %a, %b
2148 %1 = sub i32 %b, %a
2149 ret i32 0
2150 bb1:
2151 %2 = add i32 %a, %b
2152 %3 = sub i32 %b, %a
2153 ret i32 0
2154 })";
2155 LLVMContext Context;
2156 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2157
2158 std::vector<IRInstructionData *> InstrList;
2159 std::vector<unsigned> UnsignedVec;
2160
2161 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2162 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2163 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2164 getVectors(*M, Mapper, InstrList, UnsignedVec);
2165
2166 // Check to make sure that we have a long enough region.
2167 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
2168 // Check that the instructions were added correctly to both vectors.
2169 ASSERT_EQ(InstrList.size(), UnsignedVec.size());
2170
2171 std::vector<IRInstructionData *>::iterator Start, End;
2172
2173 Start = InstrList.begin();
2174 End = InstrList.begin();
2175
2176 std::advance(End, 1);
2177 IRSimilarityCandidate Cand1(0, 2, *Start, *End);
2178
2179 Start = InstrList.begin();
2180 End = InstrList.begin();
2181
2182 std::advance(Start, 3);
2183 std::advance(End, 4);
2184 IRSimilarityCandidate Cand2(3, 2, *Start, *End);
2185 DenseMap<unsigned, DenseSet<unsigned>> Mapping1;
2186 DenseMap<unsigned, DenseSet<unsigned>> Mapping2;
2187 ASSERT_TRUE(IRSimilarityCandidate::compareStructure(Cand1, Cand2, Mapping1,
2188 Mapping2));
2189 IRSimilarityCandidate::createCanonicalMappingFor(Cand1);
2190 Cand2.createCanonicalRelationFrom(Cand1, Mapping1, Mapping2);
2191
2192 for (std::pair<unsigned, DenseSet<unsigned>> &P : Mapping2) {
2193 unsigned Source = P.first;
2194
2195 ASSERT_TRUE(Cand2.getCanonicalNum(Source).has_value());
2196 unsigned Canon = *Cand2.getCanonicalNum(Source);
2197 ASSERT_TRUE(Cand1.fromCanonicalNum(Canon).has_value());
2198 unsigned Dest = *Cand1.fromCanonicalNum(Canon);
2199
2200 DenseSet<unsigned>::iterator It = P.second.find(Dest);
2201 ASSERT_NE(It, P.second.end());
2202 }
2203 }
2204
2205 // Checks that the same structure is recognized between two candidates. While
2206 // the input names are reversed, they still perform the same overall operation.
TEST(IRSimilarityCandidate,DifferentNameSameStructure)2207 TEST(IRSimilarityCandidate, DifferentNameSameStructure) {
2208 StringRef ModuleString = R"(
2209 define i32 @f(i32 %a, i32 %b) {
2210 bb0:
2211 %0 = add i32 %a, %b
2212 %1 = add i32 %b, %a
2213 ret i32 0
2214 bb1:
2215 %2 = add i32 %b, %a
2216 %3 = add i32 %a, %b
2217 ret i32 0
2218 })";
2219 LLVMContext Context;
2220 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2221
2222 std::vector<IRInstructionData *> InstrList;
2223 std::vector<unsigned> UnsignedVec;
2224
2225 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2226 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2227 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2228 getVectors(*M, Mapper, InstrList, UnsignedVec);
2229
2230 // Check to make sure that we have a long enough region.
2231 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(6));
2232 // Check that the instructions were added correctly to both vectors.
2233 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2234
2235 ASSERT_TRUE(longSimCandCompare(InstrList, true));
2236 }
2237
2238 // Checks that the same structure is recognized between two candidates when
2239 // the branches target other blocks inside the same region, the relative
2240 // distance between the blocks must be the same.
TEST(IRSimilarityCandidate,SameBranchStructureInternal)2241 TEST(IRSimilarityCandidate, SameBranchStructureInternal) {
2242 StringRef ModuleString = R"(
2243 define i32 @f(i32 %a, i32 %b) {
2244 bb0:
2245 %0 = add i32 %a, %b
2246 %1 = add i32 %b, %a
2247 br label %bb1
2248 bb1:
2249 %2 = add i32 %b, %a
2250 %3 = add i32 %a, %b
2251 ret i32 0
2252 }
2253
2254 define i32 @f2(i32 %a, i32 %b) {
2255 bb0:
2256 %0 = add i32 %a, %b
2257 %1 = add i32 %b, %a
2258 br label %bb1
2259 bb1:
2260 %2 = add i32 %b, %a
2261 %3 = add i32 %a, %b
2262 ret i32 0
2263 })";
2264 LLVMContext Context;
2265 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2266
2267 std::vector<IRInstructionData *> InstrList;
2268 std::vector<unsigned> UnsignedVec;
2269
2270 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2271 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2272 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2273 Mapper.InstClassifier.EnableBranches = true;
2274 Mapper.initializeForBBs(*M);
2275 getVectors(*M, Mapper, InstrList, UnsignedVec);
2276
2277 // Check to make sure that we have a long enough region.
2278 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));
2279 // Check that the instructions were added correctly to both vectors.
2280 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2281
2282 ASSERT_TRUE(longSimCandCompare(InstrList, true, 5, 0, 6));
2283 }
2284
2285 // Checks that the different structure is recognized between two candidates,
2286 // when the branches target other blocks inside the same region, the relative
2287 // distance between the blocks must be the same.
TEST(IRSimilarityCandidate,DifferentBranchStructureInternal)2288 TEST(IRSimilarityCandidate, DifferentBranchStructureInternal) {
2289 StringRef ModuleString = R"(
2290 define i32 @f(i32 %a, i32 %b) {
2291 bb0:
2292 %0 = add i32 %a, %b
2293 %1 = add i32 %b, %a
2294 br label %bb2
2295 bb1:
2296 %2 = add i32 %b, %a
2297 %3 = add i32 %a, %b
2298 br label %bb2
2299 bb2:
2300 %4 = add i32 %b, %a
2301 %5 = add i32 %a, %b
2302 ret i32 0
2303 }
2304
2305 define i32 @f2(i32 %a, i32 %b) {
2306 bb0:
2307 %0 = add i32 %a, %b
2308 %1 = add i32 %b, %a
2309 br label %bb1
2310 bb1:
2311 %2 = add i32 %b, %a
2312 %3 = add i32 %a, %b
2313 br label %bb2
2314 bb2:
2315 %4 = add i32 %b, %a
2316 %5 = add i32 %a, %b
2317 ret i32 0
2318 })";
2319 LLVMContext Context;
2320 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2321
2322 std::vector<IRInstructionData *> InstrList;
2323 std::vector<unsigned> UnsignedVec;
2324
2325 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2326 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2327 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2328 Mapper.InstClassifier.EnableBranches = true;
2329 Mapper.initializeForBBs(*M);
2330 getVectors(*M, Mapper, InstrList, UnsignedVec);
2331
2332 // Check to make sure that we have a long enough region.
2333 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(18));
2334 // Check that the instructions were added correctly to both vectors.
2335 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2336
2337 ASSERT_FALSE(longSimCandCompare(InstrList, true, 6, 0, 9));
2338 }
2339
2340 // Checks that the same structure is recognized between two candidates, when
2341 // the branches target other blocks outside region, the relative distance
2342 // does not need to be the same.
TEST(IRSimilarityCandidate,SameBranchStructureOutside)2343 TEST(IRSimilarityCandidate, SameBranchStructureOutside) {
2344 StringRef ModuleString = R"(
2345 define i32 @f(i32 %a, i32 %b) {
2346 bb0:
2347 %0 = add i32 %a, %b
2348 %1 = add i32 %b, %a
2349 br label %bb1
2350 bb1:
2351 %2 = add i32 %b, %a
2352 %3 = add i32 %a, %b
2353 ret i32 0
2354 }
2355
2356 define i32 @f2(i32 %a, i32 %b) {
2357 bb0:
2358 %0 = add i32 %a, %b
2359 %1 = add i32 %b, %a
2360 br label %bb1
2361 bb1:
2362 %2 = add i32 %b, %a
2363 %3 = add i32 %a, %b
2364 ret i32 0
2365 })";
2366 LLVMContext Context;
2367 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2368
2369 std::vector<IRInstructionData *> InstrList;
2370 std::vector<unsigned> UnsignedVec;
2371
2372 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2373 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2374 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2375 Mapper.InstClassifier.EnableBranches = true;
2376 Mapper.initializeForBBs(*M);
2377 getVectors(*M, Mapper, InstrList, UnsignedVec);
2378
2379 // Check to make sure that we have a long enough region.
2380 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));
2381 // Check that the instructions were added correctly to both vectors.
2382 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2383
2384 ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6));
2385 }
2386
2387 // Checks that the same structure is recognized between two candidates, when
2388 // the branches target other blocks outside region, the relative distance
2389 // does not need to be the same.
TEST(IRSimilarityCandidate,DifferentBranchStructureOutside)2390 TEST(IRSimilarityCandidate, DifferentBranchStructureOutside) {
2391 StringRef ModuleString = R"(
2392 define i32 @f(i32 %a, i32 %b) {
2393 bb0:
2394 %0 = add i32 %a, %b
2395 %1 = add i32 %b, %a
2396 br label %bb1
2397 bb1:
2398 %2 = add i32 %b, %a
2399 %3 = add i32 %a, %b
2400 ret i32 0
2401 }
2402
2403 define i32 @f2(i32 %a, i32 %b) {
2404 bb0:
2405 %0 = add i32 %a, %b
2406 %1 = add i32 %b, %a
2407 br label %bb2
2408 bb1:
2409 %2 = add i32 %b, %a
2410 %3 = add i32 %a, %b
2411 br label %bb2
2412 bb2:
2413 %4 = add i32 %b, %a
2414 %5 = add i32 %a, %b
2415 ret i32 0
2416 })";
2417 LLVMContext Context;
2418 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2419
2420 std::vector<IRInstructionData *> InstrList;
2421 std::vector<unsigned> UnsignedVec;
2422
2423 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2424 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2425 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2426 Mapper.InstClassifier.EnableBranches = true;
2427 Mapper.initializeForBBs(*M);
2428 getVectors(*M, Mapper, InstrList, UnsignedVec);
2429
2430 // Check to make sure that we have a long enough region.
2431 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(15));
2432 // Check that the instructions were added correctly to both vectors.
2433 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2434
2435 ASSERT_TRUE(longSimCandCompare(InstrList, true, 3, 0, 6));
2436 }
2437
2438 // Checks that the same structure is recognized between two candidates,
2439 // when the phi predecessor are other blocks inside the same region,
2440 // the relative distance between the blocks must be the same.
TEST(IRSimilarityCandidate,SamePHIStructureInternal)2441 TEST(IRSimilarityCandidate, SamePHIStructureInternal) {
2442 StringRef ModuleString = R"(
2443 define i32 @f(i32 %a, i32 %b) {
2444 bb0:
2445 br label %bb2
2446 bb1:
2447 br label %bb2
2448 bb2:
2449 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ]
2450 %1 = add i32 %b, %a
2451 %2 = add i32 %a, %b
2452 ret i32 0
2453 }
2454
2455 define i32 @f2(i32 %a, i32 %b) {
2456 bb0:
2457 br label %bb2
2458 bb1:
2459 br label %bb2
2460 bb2:
2461 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ]
2462 %1 = add i32 %b, %a
2463 %2 = add i32 %a, %b
2464 ret i32 0
2465 })";
2466 LLVMContext Context;
2467 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2468
2469 std::vector<IRInstructionData *> InstrList;
2470 std::vector<unsigned> UnsignedVec;
2471
2472 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2473 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2474 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2475 Mapper.InstClassifier.EnableBranches = true;
2476 Mapper.initializeForBBs(*M);
2477 getVectors(*M, Mapper, InstrList, UnsignedVec);
2478
2479 // Check to make sure that we have a long enough region.
2480 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(12));
2481 // Check that the instructions were added correctly to both vectors.
2482 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2483
2484 ASSERT_TRUE(longSimCandCompare(InstrList, true, 4, 0, 6));
2485 }
2486
2487 // Checks that the different structure is recognized between two candidates,
2488 // when the phi predecessor are other blocks inside the same region,
2489 // the relative distance between the blocks must be the same.
TEST(IRSimilarityCandidate,DifferentPHIStructureInternal)2490 TEST(IRSimilarityCandidate, DifferentPHIStructureInternal) {
2491 StringRef ModuleString = R"(
2492 define i32 @f(i32 %a, i32 %b) {
2493 bb0:
2494 br label %bb2
2495 bb1:
2496 br label %bb2
2497 bb3:
2498 br label %bb2
2499 bb2:
2500 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb1 ]
2501 %1 = add i32 %b, %a
2502 %2 = add i32 %a, %b
2503 ret i32 0
2504 }
2505
2506 define i32 @f2(i32 %a, i32 %b) {
2507 bb0:
2508 br label %bb2
2509 bb1:
2510 br label %bb2
2511 bb3:
2512 br label %bb2
2513 bb2:
2514 %0 = phi i32 [ %a, %bb0 ], [ %b, %bb3 ]
2515 %1 = add i32 %b, %a
2516 %2 = add i32 %a, %b
2517 ret i32 0
2518 })";
2519 LLVMContext Context;
2520 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2521
2522 std::vector<IRInstructionData *> InstrList;
2523 std::vector<unsigned> UnsignedVec;
2524
2525 SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;
2526 SpecificBumpPtrAllocator<IRInstructionDataList> IDLAllocator;
2527 IRInstructionMapper Mapper(&InstDataAllocator, &IDLAllocator);
2528 Mapper.InstClassifier.EnableBranches = true;
2529 Mapper.initializeForBBs(*M);
2530 getVectors(*M, Mapper, InstrList, UnsignedVec);
2531
2532 // Check to make sure that we have a long enough region.
2533 ASSERT_EQ(InstrList.size(), static_cast<unsigned>(14));
2534 // Check that the instructions were added correctly to both vectors.
2535 ASSERT_TRUE(InstrList.size() == UnsignedVec.size());
2536
2537 ASSERT_FALSE(longSimCandCompare(InstrList, true, 5, 0, 7));
2538 }
2539
2540 // Checks that two sets of identical instructions are found to be the same.
2541 // Both sequences of adds have the same operand ordering, and the same
2542 // instructions, making them strcturally equivalent.
TEST(IRSimilarityIdentifier,IdentitySimilarity)2543 TEST(IRSimilarityIdentifier, IdentitySimilarity) {
2544 StringRef ModuleString = R"(
2545 define i32 @f(i32 %a, i32 %b) {
2546 bb0:
2547 %0 = add i32 %a, %b
2548 %1 = sub i32 %b, %a
2549 br label %bb1
2550 bb1:
2551 %2 = add i32 %a, %b
2552 %3 = sub i32 %b, %a
2553 ret i32 0
2554 })";
2555 LLVMContext Context;
2556 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2557
2558 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2559 getSimilarities(*M, SimilarityCandidates);
2560
2561 ASSERT_TRUE(SimilarityCandidates.size() == 1);
2562 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
2563 ASSERT_TRUE(Cands.size() == 2);
2564 unsigned InstIdx = 0;
2565 for (IRSimilarityCandidate &Cand : Cands) {
2566 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
2567 InstIdx += 3;
2568 }
2569 }
2570 }
2571
2572 // Checks that incorrect sequences are not found as similar. In this case,
2573 // we have different sequences of instructions.
TEST(IRSimilarityIdentifier,InstructionDifference)2574 TEST(IRSimilarityIdentifier, InstructionDifference) {
2575 StringRef ModuleString = R"(
2576 define i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) {
2577 bb0:
2578 %0 = sub i32 %a, %b
2579 %1 = add i32 %b, %a
2580 br label %bb1
2581 bb1:
2582 %2 = add i32 %c, %d
2583 %3 = sub i32 %d, %c
2584 ret i32 0
2585 })";
2586 LLVMContext Context;
2587 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2588
2589 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2590 getSimilarities(*M, SimilarityCandidates);
2591
2592 ASSERT_TRUE(SimilarityCandidates.empty());
2593 }
2594
2595 // This test checks to see whether we can detect similarity for commutative
2596 // instructions where the operands have been reversed.
TEST(IRSimilarityIdentifier,CommutativeSimilarity)2597 TEST(IRSimilarityIdentifier, CommutativeSimilarity) {
2598 StringRef ModuleString = R"(
2599 define i32 @f(i32 %a, i32 %b) {
2600 bb0:
2601 %0 = add i32 %a, %b
2602 %1 = add i32 %b, %a
2603 br label %bb1
2604 bb1:
2605 %2 = add i32 %a, %b
2606 %3 = add i32 %a, %b
2607 ret i32 0
2608 })";
2609 LLVMContext Context;
2610 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2611
2612 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2613 getSimilarities(*M, SimilarityCandidates);
2614
2615 ASSERT_TRUE(SimilarityCandidates.size() == 1);
2616 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
2617 ASSERT_TRUE(Cands.size() == 2);
2618 unsigned InstIdx = 0;
2619 for (IRSimilarityCandidate &Cand : Cands) {
2620 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
2621 InstIdx += 3;
2622 }
2623 }
2624 }
2625
2626 // This test ensures that when the first instruction in a sequence is
2627 // a commutative instruction with the same value (mcomm_inst_same_val), but the
2628 // corresponding instruction (comm_inst_diff_val) is not, we mark the regions
2629 // and not similar.
TEST(IRSimilarityIdentifier,CommutativeSameValueFirstMisMatch)2630 TEST(IRSimilarityIdentifier, CommutativeSameValueFirstMisMatch) {
2631 StringRef ModuleString = R"(
2632 define void @v_1_0(i64 %v_33) {
2633 entry:
2634 %comm_inst_same_val = mul i64 undef, undef
2635 %add = add i64 %comm_inst_same_val, %v_33
2636 %comm_inst_diff_val = mul i64 0, undef
2637 %mul.i = add i64 %comm_inst_diff_val, %comm_inst_diff_val
2638 unreachable
2639 })";
2640 LLVMContext Context;
2641 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2642
2643 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2644 getSimilarities(*M, SimilarityCandidates);
2645
2646 ASSERT_TRUE(SimilarityCandidates.size() == 0);
2647 }
2648
2649 // This test makes sure that intrinsic functions that are marked commutative
2650 // are still treated as non-commutative since they are function calls.
TEST(IRSimilarityIdentifier,IntrinsicCommutative)2651 TEST(IRSimilarityIdentifier, IntrinsicCommutative) {
2652 // If treated as commutative, we will fail to find a valid mapping, causing
2653 // an assertion error.
2654 StringRef ModuleString = R"(
2655 define void @foo() {
2656 entry:
2657 %0 = call i16 @llvm.smul.fix.i16(i16 16384, i16 16384, i32 15)
2658 store i16 %0, i16* undef, align 1
2659 %1 = icmp eq i16 undef, 8192
2660 call void @bar()
2661 %2 = call i16 @llvm.smul.fix.i16(i16 -16384, i16 16384, i32 15)
2662 store i16 %2, i16* undef, align 1
2663 %3 = icmp eq i16 undef, -8192
2664 call void @bar()
2665 %4 = call i16 @llvm.smul.fix.i16(i16 -16384, i16 -16384, i32 15)
2666 ret void
2667 }
2668
2669 declare void @bar()
2670
2671 ; Function Attrs: nofree nosync nounwind readnone speculatable willreturn
2672 declare i16 @llvm.smul.fix.i16(i16, i16, i32 immarg))";
2673 LLVMContext Context;
2674 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2675
2676 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2677 getSimilarities(*M, SimilarityCandidates);
2678
2679 ASSERT_TRUE(SimilarityCandidates.size() == 0);
2680 }
2681
2682 // This test checks to see whether we can detect different structure in
2683 // commutative instructions. In this case, the second operand in the second
2684 // add is different.
TEST(IRSimilarityIdentifier,NoCommutativeSimilarity)2685 TEST(IRSimilarityIdentifier, NoCommutativeSimilarity) {
2686 StringRef ModuleString = R"(
2687 define i32 @f(i32 %a, i32 %b) {
2688 bb0:
2689 %0 = add i32 %a, %b
2690 %1 = add i32 %1, %b
2691 br label %bb1
2692 bb1:
2693 %2 = add i32 %a, %b
2694 %3 = add i32 %2, %a
2695 ret i32 0
2696 })";
2697 LLVMContext Context;
2698 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2699
2700 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2701 getSimilarities(*M, SimilarityCandidates);
2702
2703 ASSERT_TRUE(SimilarityCandidates.size() == 0);
2704 }
2705
2706 // Check that we are not finding similarity in non commutative
2707 // instructions. That is, while the instruction and operands used are the same
2708 // in the two subtraction sequences, they are in a different order, and cannot
2709 // be counted as the same since a subtraction is not commutative.
TEST(IRSimilarityIdentifier,NonCommutativeDifference)2710 TEST(IRSimilarityIdentifier, NonCommutativeDifference) {
2711 StringRef ModuleString = R"(
2712 define i32 @f(i32 %a, i32 %b) {
2713 bb0:
2714 %0 = sub i32 %a, %b
2715 %1 = sub i32 %b, %a
2716 br label %bb1
2717 bb1:
2718 %2 = sub i32 %a, %b
2719 %3 = sub i32 %a, %b
2720 ret i32 0
2721 })";
2722 LLVMContext Context;
2723 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2724
2725 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2726 getSimilarities(*M, SimilarityCandidates);
2727
2728 ASSERT_TRUE(SimilarityCandidates.empty());
2729 }
2730
2731 // Check that we find similarity despite changing the register names.
TEST(IRSimilarityIdentifier,MappingSimilarity)2732 TEST(IRSimilarityIdentifier, MappingSimilarity) {
2733 StringRef ModuleString = R"(
2734 define i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) {
2735 bb0:
2736 %0 = add i32 %a, %b
2737 %1 = sub i32 %b, %a
2738 br label %bb1
2739 bb1:
2740 %2 = add i32 %c, %d
2741 %3 = sub i32 %d, %c
2742 ret i32 0
2743 })";
2744 LLVMContext Context;
2745 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2746
2747 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2748 getSimilarities(*M, SimilarityCandidates);
2749
2750 ASSERT_TRUE(SimilarityCandidates.size() == 1);
2751 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
2752 ASSERT_TRUE(Cands.size() == 2);
2753 unsigned InstIdx = 0;
2754 for (IRSimilarityCandidate &Cand : Cands) {
2755 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
2756 InstIdx += 3;
2757 }
2758 }
2759 }
2760
2761 // Check that we find instances of swapped predicate isomorphism. That is,
2762 // for predicates that can be flipped, e.g. greater than to less than,
2763 // we can identify that instances of these different literal predicates, but are
2764 // the same within a single swap can be found.
TEST(IRSimilarityIdentifier,PredicateIsomorphism)2765 TEST(IRSimilarityIdentifier, PredicateIsomorphism) {
2766 StringRef ModuleString = R"(
2767 define i32 @f(i32 %a, i32 %b) {
2768 bb0:
2769 %0 = add i32 %a, %b
2770 %1 = icmp sgt i32 %b, %a
2771 br label %bb1
2772 bb1:
2773 %2 = add i32 %a, %b
2774 %3 = icmp slt i32 %a, %b
2775 ret i32 0
2776 })";
2777 LLVMContext Context;
2778 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2779
2780 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2781 getSimilarities(*M, SimilarityCandidates);
2782
2783 ASSERT_TRUE(SimilarityCandidates.size() == 1);
2784 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
2785 ASSERT_TRUE(Cands.size() == 2);
2786 unsigned InstIdx = 0;
2787 for (IRSimilarityCandidate &Cand : Cands) {
2788 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
2789 InstIdx += 3;
2790 }
2791 }
2792 }
2793
2794 // Checks that constants are detected as the same operand in each use in the
2795 // sequences of instructions. Also checks that we can find structural
2796 // equivalence using constants. In this case the 1 has the same use pattern as
2797 // %a.
TEST(IRSimilarityIdentifier,ConstantMappingSimilarity)2798 TEST(IRSimilarityIdentifier, ConstantMappingSimilarity) {
2799 StringRef ModuleString = R"(
2800 define i32 @f(i32 %a, i32 %b) {
2801 bb0:
2802 %0 = add i32 1, %b
2803 %1 = icmp sgt i32 %b, 1
2804 br label %bb1
2805 bb1:
2806 %2 = add i32 %a, %b
2807 %3 = icmp sgt i32 %b, %a
2808 ret i32 0
2809 })";
2810 LLVMContext Context;
2811 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2812
2813 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2814 getSimilarities(*M, SimilarityCandidates);
2815
2816 ASSERT_TRUE(SimilarityCandidates.size() == 1);
2817 for (std::vector<IRSimilarityCandidate> &Cands : SimilarityCandidates) {
2818 ASSERT_TRUE(Cands.size() == 2);
2819 unsigned InstIdx = 0;
2820 for (IRSimilarityCandidate &Cand : Cands) {
2821 ASSERT_TRUE(Cand.getStartIdx() == InstIdx);
2822 InstIdx += 3;
2823 }
2824 }
2825 }
2826
2827 // Check that constants are uniquely identified. i.e. two different constants
2828 // are not considered the same. This means that this should not find any
2829 // structural similarity.
TEST(IRSimilarityIdentifier,ConstantMappingDifference)2830 TEST(IRSimilarityIdentifier, ConstantMappingDifference) {
2831 StringRef ModuleString = R"(
2832 define i32 @f(i32 %a, i32 %b) {
2833 bb0:
2834 %0 = add i32 1, %b
2835 %1 = icmp sgt i32 %b, 2
2836 br label %bb1
2837 bb1:
2838 %2 = add i32 %a, %b
2839 %3 = icmp slt i32 %a, %b
2840 ret i32 0
2841 })";
2842 LLVMContext Context;
2843 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
2844
2845 std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2846 getSimilarities(*M, SimilarityCandidates);
2847
2848 ASSERT_TRUE(SimilarityCandidates.empty());
2849 }
2850