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
25	static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
26	StringRef ModuleStr) {
27	SMDiagnostic Err;
28	std::unique_ptr<Module> M = parseAssemblyString(AsmString: ModuleStr, Err, Context);
29	assert(M && "Bad LLVM IR?");
30	return M;
31	}
32
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, IntegerMapping&: UnsignedVec);
39	}
40
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
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *M);
752	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
782	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
809	getVectors(M&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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(i&: End, n: StartIdxOne + Length - 1);
1757	IRSimilarityCandidate Cand1(StartIdxOne, Length, *Start, *End);
1758
1759	Start = InstrList.begin();
1760	End = InstrList.begin();
1761
1762	std::advance(i&: Start, n: StartIdxTwo);
1763	std::advance(i&: End, n: StartIdxTwo + Length - 1);
1764	IRSimilarityCandidate Cand2(StartIdxTwo, Length, *Start, *End);
1765	if (Structure)
1766	return IRSimilarityCandidate::compareStructure(A: Cand1, B: Cand2);
1767	return IRSimilarityCandidate::isSimilar(A: Cand1, B: Cand2);
1768	}
1769
1770	// Checks that two adds with commuted operands are considered to be the same
1771	// instructions.
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, ModuleStr: 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&: *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(i&: End, n: 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.
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, ModuleStr: 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&: *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(i&: End, n: 1);
1839	IRSimilarityCandidate Cand1(0, 2, *Start, *End);
1840
1841	Start = InstrList.begin();
1842	End = InstrList.begin();
1843
1844	std::advance(i&: Start, n: 3);
1845	std::advance(i&: End, n: 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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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(i&: End, n: 2);
1999	IRSimilarityCandidate Cand1(0, 3, *Start, *End);
2000
2001	Start = InstrList.begin();
2002	End = InstrList.begin();
2003
2004	std::advance(i&: Start, n: 3);
2005	std::advance(i&: End, n: 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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *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(i&: End, n: 1);
2173	IRSimilarityCandidate Cand1(0, 2, *Start, *End);
2174
2175	Start = InstrList.begin();
2176	End = InstrList.begin();
2177
2178	std::advance(i&: Start, n: 3);
2179	std::advance(i&: End, n: 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(CurrCand&: Cand1);
2186	Cand2.createCanonicalRelationFrom(SourceCand&: Cand1, ToSourceMapping&: Mapping1, FromSourceMapping&: 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(N: Source);
2193	ASSERT_TRUE(Cand1.fromCanonicalNum(Canon).has_value());
2194	unsigned Dest = *Cand1.fromCanonicalNum(N: Canon);
2195
2196	DenseSet<unsigned>::iterator It = P.second.find(V: 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.
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, ModuleStr: 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&: *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.
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, ModuleStr: 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&: *M);
2271	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
2326	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
2373	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
2424	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
2473	getVectors(M&: *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.
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, ModuleStr: 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&: *M);
2526	getVectors(M&: *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.
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, ModuleStr: ModuleString);
2553
2554	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2555	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2584
2585	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2586	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2607
2608	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2609	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2638
2639	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2640	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2671
2672	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2673	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2695
2696	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2697	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2720
2721	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2722	getSimilarities(M&: *M, SimilarityCandidates);
2723
2724	ASSERT_TRUE(SimilarityCandidates.empty());
2725	}
2726
2727	// Check that we find similarity despite changing the register names.
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, ModuleStr: ModuleString);
2742
2743	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2744	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2775
2776	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2777	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2808
2809	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2810	getSimilarities(M&: *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.
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, ModuleStr: ModuleString);
2840
2841	std::vector<std::vector<IRSimilarityCandidate>> SimilarityCandidates;
2842	getSimilarities(M&: *M, SimilarityCandidates);
2843
2844	ASSERT_TRUE(SimilarityCandidates.empty());
2845	}
2846