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