1 //===- InjectorIRStrategyTest.cpp - Tests for injector strategy -----------===//
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 #include "llvm/ADT/DenseMap.h"
10 #include "llvm/ADT/StringRef.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/AsmParser/SlotMapping.h"
13 #include "llvm/FuzzMutate/IRMutator.h"
14 #include "llvm/FuzzMutate/Operations.h"
15 #include "llvm/FuzzMutate/RandomIRBuilder.h"
16 #include "llvm/IR/FMF.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/LLVMContext.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/IR/Verifier.h"
21 #include "llvm/Support/SourceMgr.h"
22 #include <random>
23
24 #include "gtest/gtest.h"
25
26 using namespace llvm;
27
28 static constexpr int Seed = 5;
29
30 namespace {
31
createInjectorMutator()32 std::unique_ptr<IRMutator> createInjectorMutator() {
33 std::vector<TypeGetter> Types{
34 Type::getInt1Ty, Type::getInt8Ty, Type::getInt16Ty, Type::getInt32Ty,
35 Type::getInt64Ty, Type::getFloatTy, Type::getDoubleTy};
36
37 // Add vector 1, 2, 3, 4, and 8.
38 int VectorLength[] = {1, 2, 3, 4, 8};
39 std::vector<TypeGetter> BasicTypeGetters(Types);
40 for (auto typeGetter : BasicTypeGetters) {
41 for (int length : VectorLength) {
42 Types.push_back([typeGetter, length](LLVMContext &C) {
43 return VectorType::get(typeGetter(C), length, false);
44 });
45 }
46 }
47
48 std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
49 Strategies.push_back(std::make_unique<InjectorIRStrategy>(
50 InjectorIRStrategy::getDefaultOps()));
51
52 return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
53 }
54
createMutator()55 template <class Strategy> std::unique_ptr<IRMutator> createMutator() {
56 std::vector<TypeGetter> Types{
57 Type::getInt1Ty, Type::getInt8Ty, Type::getInt16Ty, Type::getInt32Ty,
58 Type::getInt64Ty, Type::getFloatTy, Type::getDoubleTy};
59
60 std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
61 Strategies.push_back(std::make_unique<Strategy>());
62
63 return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
64 }
65
parseAssembly(const char * Assembly,LLVMContext & Context)66 std::unique_ptr<Module> parseAssembly(const char *Assembly,
67 LLVMContext &Context) {
68
69 SMDiagnostic Error;
70 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
71
72 std::string ErrMsg;
73 raw_string_ostream OS(ErrMsg);
74 Error.print("", OS);
75
76 assert(M && !verifyModule(*M, &errs()));
77 return M;
78 }
79
IterateOnSource(StringRef Source,IRMutator & Mutator)80 void IterateOnSource(StringRef Source, IRMutator &Mutator) {
81 LLVMContext Ctx;
82
83 for (int i = 0; i < 10; ++i) {
84 auto M = parseAssembly(Source.data(), Ctx);
85 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
86
87 Mutator.mutateModule(*M, Seed, IRMutator::getModuleSize(*M) + 100);
88 EXPECT_TRUE(!verifyModule(*M, &errs()));
89 }
90 }
91
mutateAndVerifyModule(StringRef Source,std::unique_ptr<IRMutator> & Mutator,int repeat=100)92 static void mutateAndVerifyModule(StringRef Source,
93 std::unique_ptr<IRMutator> &Mutator,
94 int repeat = 100) {
95 LLVMContext Ctx;
96 auto M = parseAssembly(Source.data(), Ctx);
97 std::mt19937 mt(Seed);
98 std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
99 for (int i = 0; i < repeat; i++) {
100 Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 1024);
101 ASSERT_FALSE(verifyModule(*M, &errs()));
102 }
103 }
104 template <class Strategy>
mutateAndVerifyModule(StringRef Source,int repeat=100)105 static void mutateAndVerifyModule(StringRef Source, int repeat = 100) {
106 auto Mutator = createMutator<Strategy>();
107 ASSERT_TRUE(Mutator);
108 mutateAndVerifyModule(Source, Mutator, repeat);
109 }
110
TEST(InjectorIRStrategyTest,EmptyModule)111 TEST(InjectorIRStrategyTest, EmptyModule) {
112 // Test that we can inject into empty module
113
114 LLVMContext Ctx;
115 auto M = std::make_unique<Module>("M", Ctx);
116 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
117
118 auto Mutator = createInjectorMutator();
119 ASSERT_TRUE(Mutator);
120
121 Mutator->mutateModule(*M, Seed, IRMutator::getModuleSize(*M) + 1);
122 EXPECT_TRUE(!verifyModule(*M, &errs()));
123 }
124
TEST(InjectorIRStrategyTest,LargeInsertion)125 TEST(InjectorIRStrategyTest, LargeInsertion) {
126 StringRef Source = "";
127 auto Mutator = createInjectorMutator();
128 ASSERT_TRUE(Mutator);
129 mutateAndVerifyModule(Source, Mutator, 100);
130 }
131
TEST(InjectorIRStrategyTest,InsertWMustTailCall)132 TEST(InjectorIRStrategyTest, InsertWMustTailCall) {
133 StringRef Source = "\n\
134 define i1 @recursive() { \n\
135 Entry: \n\
136 %Ret = musttail call i1 @recursive() \n\
137 ret i1 %Ret \n\
138 }";
139 auto Mutator = createInjectorMutator();
140 ASSERT_TRUE(Mutator);
141 mutateAndVerifyModule(Source, Mutator, 100);
142 }
143
TEST(InjectorIRStrategyTest,InsertWTailCall)144 TEST(InjectorIRStrategyTest, InsertWTailCall) {
145 StringRef Source = "\n\
146 define i1 @recursive() { \n\
147 Entry: \n\
148 %Ret = tail call i1 @recursive() \n\
149 ret i1 %Ret \n\
150 }";
151 auto Mutator = createInjectorMutator();
152 ASSERT_TRUE(Mutator);
153 mutateAndVerifyModule(Source, Mutator, 100);
154 }
155
TEST(InstDeleterIRStrategyTest,EmptyFunction)156 TEST(InstDeleterIRStrategyTest, EmptyFunction) {
157 // Test that we don't crash even if we can't remove from one of the functions.
158
159 StringRef Source = ""
160 "define <8 x i32> @func1() {\n"
161 "ret <8 x i32> undef\n"
162 "}\n"
163 "\n"
164 "define i32 @func2() {\n"
165 "%A9 = alloca i32\n"
166 "%L6 = load i32, i32* %A9\n"
167 "ret i32 %L6\n"
168 "}\n";
169
170 auto Mutator = createMutator<InstDeleterIRStrategy>();
171 ASSERT_TRUE(Mutator);
172
173 IterateOnSource(Source, *Mutator);
174 }
175
TEST(InstDeleterIRStrategyTest,PhiNodes)176 TEST(InstDeleterIRStrategyTest, PhiNodes) {
177 // Test that inst deleter works correctly with the phi nodes.
178
179 LLVMContext Ctx;
180 StringRef Source = "\n\
181 define i32 @earlyreturncrash(i32 %x) {\n\
182 entry:\n\
183 switch i32 %x, label %sw.epilog [\n\
184 i32 1, label %sw.bb1\n\
185 ]\n\
186 \n\
187 sw.bb1:\n\
188 br label %sw.epilog\n\
189 \n\
190 sw.epilog:\n\
191 %a.0 = phi i32 [ 7, %entry ], [ 9, %sw.bb1 ]\n\
192 %b.0 = phi i32 [ 10, %entry ], [ 4, %sw.bb1 ]\n\
193 ret i32 %a.0\n\
194 }";
195
196 auto Mutator = createMutator<InstDeleterIRStrategy>();
197 ASSERT_TRUE(Mutator);
198
199 IterateOnSource(Source, *Mutator);
200 }
201
checkModifyNoUnsignedAndNoSignedWrap(StringRef Opc)202 static void checkModifyNoUnsignedAndNoSignedWrap(StringRef Opc) {
203 LLVMContext Ctx;
204 std::string Source = std::string("\n\
205 define i32 @test(i32 %x) {\n\
206 %a = ") + Opc.str() +
207 std::string(" i32 %x, 10\n\
208 ret i32 %a\n\
209 }");
210
211 auto Mutator = createMutator<InstModificationIRStrategy>();
212 ASSERT_TRUE(Mutator);
213
214 auto M = parseAssembly(Source.data(), Ctx);
215 auto &F = *M->begin();
216 auto *AddI = &*F.begin()->begin();
217 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
218 bool FoundNUW = false;
219 bool FoundNSW = false;
220 for (int i = 0; i < 100; ++i) {
221 Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
222 EXPECT_TRUE(!verifyModule(*M, &errs()));
223 FoundNUW |= AddI->hasNoUnsignedWrap();
224 FoundNSW |= AddI->hasNoSignedWrap();
225 }
226
227 // The mutator should have added nuw and nsw during some mutations.
228 EXPECT_TRUE(FoundNUW);
229 EXPECT_TRUE(FoundNSW);
230 }
TEST(InstModificationIRStrategyTest,Add)231 TEST(InstModificationIRStrategyTest, Add) {
232 checkModifyNoUnsignedAndNoSignedWrap("add");
233 }
234
TEST(InstModificationIRStrategyTest,Sub)235 TEST(InstModificationIRStrategyTest, Sub) {
236 checkModifyNoUnsignedAndNoSignedWrap("sub");
237 }
238
TEST(InstModificationIRStrategyTest,Mul)239 TEST(InstModificationIRStrategyTest, Mul) {
240 checkModifyNoUnsignedAndNoSignedWrap("mul");
241 }
242
TEST(InstModificationIRStrategyTest,Shl)243 TEST(InstModificationIRStrategyTest, Shl) {
244 checkModifyNoUnsignedAndNoSignedWrap("shl");
245 }
246
TEST(InstModificationIRStrategyTest,ICmp)247 TEST(InstModificationIRStrategyTest, ICmp) {
248 LLVMContext Ctx;
249 StringRef Source = "\n\
250 define i1 @test(i32 %x) {\n\
251 %a = icmp eq i32 %x, 10\n\
252 ret i1 %a\n\
253 }";
254
255 auto Mutator = createMutator<InstModificationIRStrategy>();
256 ASSERT_TRUE(Mutator);
257
258 auto M = parseAssembly(Source.data(), Ctx);
259 auto &F = *M->begin();
260 CmpInst *CI = cast<CmpInst>(&*F.begin()->begin());
261 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
262 bool FoundNE = false;
263 for (int i = 0; i < 100; ++i) {
264 Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
265 EXPECT_TRUE(!verifyModule(*M, &errs()));
266 FoundNE |= CI->getPredicate() == CmpInst::ICMP_NE;
267 }
268
269 EXPECT_TRUE(FoundNE);
270 }
271
TEST(InstModificationIRStrategyTest,FCmp)272 TEST(InstModificationIRStrategyTest, FCmp) {
273 LLVMContext Ctx;
274 StringRef Source = "\n\
275 define i1 @test(float %x) {\n\
276 %a = fcmp oeq float %x, 10.0\n\
277 ret i1 %a\n\
278 }";
279
280 auto Mutator = createMutator<InstModificationIRStrategy>();
281 ASSERT_TRUE(Mutator);
282
283 auto M = parseAssembly(Source.data(), Ctx);
284 auto &F = *M->begin();
285 CmpInst *CI = cast<CmpInst>(&*F.begin()->begin());
286 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
287 bool FoundONE = false;
288 for (int i = 0; i < 100; ++i) {
289 Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
290 EXPECT_TRUE(!verifyModule(*M, &errs()));
291 FoundONE |= CI->getPredicate() == CmpInst::FCMP_ONE;
292 }
293
294 EXPECT_TRUE(FoundONE);
295 }
296
TEST(InstModificationIRStrategyTest,GEP)297 TEST(InstModificationIRStrategyTest, GEP) {
298 LLVMContext Ctx;
299 StringRef Source = "\n\
300 define i32* @test(i32* %ptr) {\n\
301 %gep = getelementptr i32, i32* %ptr, i32 10\n\
302 ret i32* %gep\n\
303 }";
304
305 auto Mutator = createMutator<InstModificationIRStrategy>();
306 ASSERT_TRUE(Mutator);
307
308 auto M = parseAssembly(Source.data(), Ctx);
309 auto &F = *M->begin();
310 GetElementPtrInst *GEP = cast<GetElementPtrInst>(&*F.begin()->begin());
311 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
312 bool FoundInbounds = false;
313 for (int i = 0; i < 100; ++i) {
314 Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
315 EXPECT_TRUE(!verifyModule(*M, &errs()));
316 FoundInbounds |= GEP->isInBounds();
317 }
318
319 EXPECT_TRUE(FoundInbounds);
320 }
321
322 /// The caller has to guarantee that function argument are used in the SAME
323 /// place as the operand.
VerfyOperandShuffled(StringRef Source,std::pair<int,int> ShuffleItems)324 void VerfyOperandShuffled(StringRef Source, std::pair<int, int> ShuffleItems) {
325 LLVMContext Ctx;
326 auto Mutator = createMutator<InstModificationIRStrategy>();
327 ASSERT_TRUE(Mutator);
328
329 auto M = parseAssembly(Source.data(), Ctx);
330 auto &F = *M->begin();
331 Instruction *Inst = &*F.begin()->begin();
332 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
333 ASSERT_TRUE(Inst->getOperand(ShuffleItems.first) ==
334 dyn_cast<Value>(F.getArg(ShuffleItems.first)));
335 ASSERT_TRUE(Inst->getOperand(ShuffleItems.second) ==
336 dyn_cast<Value>(F.getArg(ShuffleItems.second)));
337
338 Mutator->mutateModule(*M, 0, IRMutator::getModuleSize(*M) + 100);
339 ASSERT_TRUE(!verifyModule(*M, &errs()));
340
341 ASSERT_TRUE(Inst->getOperand(ShuffleItems.first) ==
342 dyn_cast<Value>(F.getArg(ShuffleItems.second)));
343 ASSERT_TRUE(Inst->getOperand(ShuffleItems.second) ==
344 dyn_cast<Value>(F.getArg(ShuffleItems.first)));
345 }
346
TEST(InstModificationIRStrategyTest,ShuffleAnd)347 TEST(InstModificationIRStrategyTest, ShuffleAnd) {
348 StringRef Source = "\n\
349 define i32 @test(i32 %0, i32 %1) {\n\
350 %add = and i32 %0, %1\n\
351 ret i32 %add\n\
352 }";
353 VerfyOperandShuffled(Source, {0, 1});
354 }
TEST(InstModificationIRStrategyTest,ShuffleSelect)355 TEST(InstModificationIRStrategyTest, ShuffleSelect) {
356 StringRef Source = "\n\
357 define i32 @test(i1 %0, i32 %1, i32 %2) {\n\
358 %select = select i1 %0, i32 %1, i32 %2\n\
359 ret i32 %select\n\
360 }";
361 VerfyOperandShuffled(Source, {1, 2});
362 }
363
VerfyDivDidntShuffle(StringRef Source)364 void VerfyDivDidntShuffle(StringRef Source) {
365 LLVMContext Ctx;
366 auto Mutator = createMutator<InstModificationIRStrategy>();
367 ASSERT_TRUE(Mutator);
368
369 auto M = parseAssembly(Source.data(), Ctx);
370 auto &F = *M->begin();
371 Instruction *Inst = &*F.begin()->begin();
372 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
373
374 EXPECT_TRUE(isa<Constant>(Inst->getOperand(0)));
375 EXPECT_TRUE(Inst->getOperand(1) == dyn_cast<Value>(F.getArg(0)));
376
377 Mutator->mutateModule(*M, Seed, IRMutator::getModuleSize(*M) + 100);
378 EXPECT_TRUE(!verifyModule(*M, &errs()));
379
380 // Didn't shuffle.
381 EXPECT_TRUE(isa<Constant>(Inst->getOperand(0)));
382 EXPECT_TRUE(Inst->getOperand(1) == dyn_cast<Value>(F.getArg(0)));
383 }
TEST(InstModificationIRStrategyTest,DidntShuffleSDiv)384 TEST(InstModificationIRStrategyTest, DidntShuffleSDiv) {
385 StringRef Source = "\n\
386 define i32 @test(i32 %0) {\n\
387 %div = sdiv i32 0, %0\n\
388 ret i32 %div\n\
389 }";
390 VerfyDivDidntShuffle(Source);
391 }
TEST(InstModificationIRStrategyTest,DidntShuffleFRem)392 TEST(InstModificationIRStrategyTest, DidntShuffleFRem) {
393 StringRef Source = "\n\
394 define <2 x double> @test(<2 x double> %0) {\n\
395 %div = frem <2 x double> <double 0.0, double 0.0>, %0\n\
396 ret <2 x double> %div\n\
397 }";
398 VerfyDivDidntShuffle(Source);
399 }
400
TEST(InsertFunctionStrategy,Func)401 TEST(InsertFunctionStrategy, Func) {
402 LLVMContext Ctx;
403 const char *Source = "";
404 auto Mutator = createMutator<InsertFunctionStrategy>();
405 ASSERT_TRUE(Mutator);
406
407 auto M = parseAssembly(Source, Ctx);
408 srand(Seed);
409 for (int i = 0; i < 100; i++) {
410 Mutator->mutateModule(*M, rand(), 1024);
411 EXPECT_TRUE(!verifyModule(*M, &errs()));
412 }
413 }
414
TEST(InsertFunctionStrategy,AvoidCallingFunctionWithSpecialParam)415 TEST(InsertFunctionStrategy, AvoidCallingFunctionWithSpecialParam) {
416 LLVMContext Ctx;
417 StringRef Source = "\n\
418 declare void @llvm.dbg.value(metadata %0, metadata %1, metadata %2)\n\
419 declare i1 @llvm.experimental.gc.result.i1(token %0)\n\
420 define i32 @test(i32 %0) gc \"statepoint-example\" {\n\
421 ret i32 %0 \n\
422 }";
423 auto Mutator = createMutator<InsertFunctionStrategy>();
424 auto M = parseAssembly(Source.data(), Ctx);
425 srand(Seed);
426 for (int i = 0; i < 100; i++) {
427 Mutator->mutateModule(*M, rand(), 1024);
428 EXPECT_TRUE(!verifyModule(*M, &errs()));
429 }
430 }
431
TEST(InstModificationIRStrategy,Exact)432 TEST(InstModificationIRStrategy, Exact) {
433 LLVMContext Ctx;
434 StringRef Source = "\n\
435 define i32 @test(i32 %a, i32 %b) {\n\
436 %c = ashr i32 %a, %b \n\
437 ret i32 %c\n\
438 }";
439
440 auto Mutator = createMutator<InstModificationIRStrategy>();
441 ASSERT_TRUE(Mutator);
442
443 std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx);
444 std::mt19937 mt(Seed);
445 std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
446 auto &F = *M->begin();
447 BinaryOperator *AShr = cast<BinaryOperator>(&*F.begin()->begin());
448 bool FoundExact = false;
449 for (int i = 0; i < 100; ++i) {
450 Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 100);
451 ASSERT_FALSE(verifyModule(*M, &errs()));
452 FoundExact |= AShr->isExact();
453 }
454
455 EXPECT_TRUE(FoundExact);
456 }
TEST(InstModificationIRStrategy,FastMath)457 TEST(InstModificationIRStrategy, FastMath) {
458 LLVMContext Ctx;
459 StringRef Source = "\n\
460 declare [4 x <4 x double>] @vecdouble(double) \n\
461 define double @test(i1 %C, double %a, double %b) { \n\
462 Entry: \n\
463 br i1 %C, label %True, label %False \n\
464 True: \n\
465 br label %Exit \n\
466 False: \n\
467 br label %Exit \n\
468 Exit: \n\
469 %PHIi32 = phi i32 [1, %True], [2, %False] \n\
470 %PHIdouble = phi double [%a, %True], [%b, %False] \n\
471 %Call = call [4 x <4 x double>] @vecdouble(double %PHIdouble) \n\
472 %c = fneg double %PHIdouble \n\
473 %s = select i1 %C, double %a, double %b \n\
474 %d = fadd double %s, %c \n\
475 ret double %d \n\
476 }";
477
478 auto Mutator = createMutator<InstModificationIRStrategy>();
479 ASSERT_TRUE(Mutator);
480
481 std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx);
482 std::mt19937 mt(Seed);
483 std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
484 DenseMap<Instruction *, bool> FPOpsHasFastMath;
485 for (auto &F : *M) {
486 for (auto &BB : F) {
487 for (auto &I : BB) {
488 Type *Ty = I.getType();
489 if (Ty->isFPOrFPVectorTy() || Ty->isArrayTy()) {
490 FPOpsHasFastMath[&I] = false;
491 }
492 }
493 }
494 }
495 ASSERT_TRUE(M && !verifyModule(*M, &errs()));
496 for (int i = 0; i < 300; ++i) {
497 Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 100);
498 for (auto p : FPOpsHasFastMath)
499 FPOpsHasFastMath[p.first] |= p.first->getFastMathFlags().any();
500 ASSERT_FALSE(verifyModule(*M, &errs()));
501 }
502 for (auto p : FPOpsHasFastMath)
503 ASSERT_TRUE(p.second);
504 }
505
TEST(InsertCFGStrategy,CFG)506 TEST(InsertCFGStrategy, CFG) {
507 StringRef Source = "\n\
508 define i32 @test(i1 %C1, i1 %C2, i1 %C3, i16 %S1, i16 %S2, i32 %I1) { \n\
509 Entry: \n\
510 %I2 = add i32 %I1, 1 \n\
511 %C = and i1 %C1, %C2 \n\
512 br label %Body \n\
513 Body: \n\
514 %IB = add i32 %I1, %I2 \n\
515 %CB = and i1 %C1, %C \n\
516 br label %Exit \n\
517 Exit: \n\
518 %IE = add i32 %IB, %I2 \n\
519 %CE = and i1 %CB, %C \n\
520 ret i32 %IE \n\
521 }";
522 mutateAndVerifyModule<InsertCFGStrategy>(Source);
523 }
524
TEST(InsertPHIStrategy,PHI)525 TEST(InsertPHIStrategy, PHI) {
526 StringRef Source = "\n\
527 define void @test(i1 %C1, i1 %C2, i32 %I, double %FP) { \n\
528 Entry: \n\
529 %C = and i1 %C1, %C2 \n\
530 br i1 %C, label %LoopHead, label %Exit \n\
531 LoopHead: ; pred Entry, LoopBody \n\
532 switch i32 %I, label %Default [ \n\
533 i32 1, label %OnOne \n\
534 i32 2, label %OnTwo \n\
535 i32 3, label %OnThree \n\
536 ] \n\
537 Default: \n\
538 br label %LoopBody \n\
539 OnOne: ; pred LoopHead \n\
540 %DFP = fmul double %FP, 2.0 \n\
541 %OnOneCond = fcmp ogt double %DFP, %FP \n\
542 br i1 %OnOneCond, label %LoopBody, label %Exit \n\
543 OnTwo: ; pred Entry \n\
544 br i1 %C1, label %OnThree, label %LoopBody \n\
545 OnThree: ; pred Entry, OnTwo, OnThree \n\
546 br i1 %C2, label %OnThree, label %LoopBody \n\
547 LoopBody: ; pred Default, OnOne, OnTwo, OnThree \n\
548 br label %LoopHead \n\
549 Exit: ; pred Entry, OnOne \n\
550 ret void \n\
551 }";
552 mutateAndVerifyModule<InsertPHIStrategy>(Source);
553 }
554
TEST(InsertPHIStrategy,PHIWithSameIncomingBlock)555 TEST(InsertPHIStrategy, PHIWithSameIncomingBlock) {
556 LLVMContext Ctx;
557 StringRef Source = "\n\
558 define void @test(i32 %I) { \n\
559 Entry: \n\
560 switch i32 %I, label %Exit [ \n\
561 i32 1, label %IdentCase \n\
562 i32 2, label %IdentCase \n\
563 i32 3, label %IdentCase \n\
564 i32 4, label %IdentCase \n\
565 ] \n\
566 IdentCase: \n\
567 br label %Exit \n\
568 Exit: \n\
569 ret void \n\
570 }";
571 auto IPS = std::make_unique<InsertPHIStrategy>();
572 RandomIRBuilder IB(Seed, {IntegerType::getInt32Ty(Ctx)});
573 auto M = parseAssembly(Source.data(), Ctx);
574 Function &F = *M->begin();
575 for (auto &BB : F) {
576 IPS->mutate(BB, IB);
577 ASSERT_FALSE(verifyModule(*M, &errs()));
578 }
579 }
580
TEST(SinkInstructionStrategy,Operand)581 TEST(SinkInstructionStrategy, Operand) {
582 StringRef Source = "\n\
583 define i32 @test(i1 %C1, i1 %C2, i1 %C3, i32 %I, i32 %J) { \n\
584 Entry: \n\
585 %I100 = add i32 %I, 100 \n\
586 switch i32 %I100, label %BB0 [ \n\
587 i32 42, label %BB1 \n\
588 ] \n\
589 BB0: \n\
590 %IAJ = add i32 %I, %J \n\
591 %ISJ = sub i32 %I, %J \n\
592 br label %Exit \n\
593 BB1: \n\
594 %IJ = mul i32 %I, %J \n\
595 %C = and i1 %C2, %C3 \n\
596 br i1 %C, label %BB0, label %Exit \n\
597 Exit: \n\
598 ret i32 %I \n\
599 }";
600 mutateAndVerifyModule<SinkInstructionStrategy>(Source);
601 }
602
TEST(SinkInstructionStrategy,DoNotSinkTokenType)603 TEST(SinkInstructionStrategy, DoNotSinkTokenType) {
604 StringRef Source = "\n\
605 declare ptr @fake_personality_function() \n\
606 declare token @llvm.experimental.gc.statepoint.p0(i64 immarg %0, i32 immarg %1, ptr %2, i32 immarg %3, i32 immarg %4, ...) \n\
607 define void @test() gc \"statepoint-example\" personality ptr @fake_personality_function { \n\
608 Entry: \n\
609 %token1 = call token (i64, i32, ptr, i32, i32, ...) \
610 @llvm.experimental.gc.statepoint.p0(i64 0, i32 0, ptr elementtype(ptr addrspace(1) ()) undef, i32 0, i32 0, i32 0, i32 0) \n\
611 ret void \n\
612 }";
613 mutateAndVerifyModule<SinkInstructionStrategy>(Source);
614 }
615
VerifyBlockShuffle(StringRef Source)616 static void VerifyBlockShuffle(StringRef Source) {
617 LLVMContext Ctx;
618 auto Mutator = createMutator<ShuffleBlockStrategy>();
619 ASSERT_TRUE(Mutator);
620
621 std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx);
622 Function *F = &*M->begin();
623 DenseMap<BasicBlock *, int> PreShuffleInstCnt;
624 for (BasicBlock &BB : *F) {
625 PreShuffleInstCnt.insert({&BB, BB.size()});
626 }
627 std::mt19937 mt(Seed);
628 std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
629 for (int i = 0; i < 100; i++) {
630 Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 1024);
631 for (BasicBlock &BB : *F) {
632 int PostShuffleIntCnt = BB.size();
633 EXPECT_EQ(PostShuffleIntCnt, PreShuffleInstCnt[&BB]);
634 }
635 EXPECT_FALSE(verifyModule(*M, &errs()));
636 }
637 }
638
TEST(ShuffleBlockStrategy,ShuffleBlocks)639 TEST(ShuffleBlockStrategy, ShuffleBlocks) {
640 StringRef Source = "\n\
641 define i64 @test(i1 %0, i1 %1, i1 %2, i32 %3, i32 %4) { \n\
642 Entry: \n\
643 %A = alloca i32, i32 8, align 4 \n\
644 %E.1 = and i32 %3, %4 \n\
645 %E.2 = add i32 %4 , 1 \n\
646 %A.GEP.1 = getelementptr i32, ptr %A, i32 0 \n\
647 %A.GEP.2 = getelementptr i32, ptr %A.GEP.1, i32 1 \n\
648 %L.2 = load i32, ptr %A.GEP.2 \n\
649 %L.1 = load i32, ptr %A.GEP.1 \n\
650 %E.3 = sub i32 %E.2, %L.1 \n\
651 %Cond.1 = icmp eq i32 %E.3, %E.2 \n\
652 %Cond.2 = and i1 %0, %1 \n\
653 %Cond = or i1 %Cond.1, %Cond.2 \n\
654 br i1 %Cond, label %BB0, label %BB1 \n\
655 BB0: \n\
656 %Add = add i32 %L.1, %L.2 \n\
657 %Sub = sub i32 %L.1, %L.2 \n\
658 %Sub.1 = sub i32 %Sub, 12 \n\
659 %Cast.1 = bitcast i32 %4 to float \n\
660 %Add.2 = add i32 %3, 1 \n\
661 %Cast.2 = bitcast i32 %Add.2 to float \n\
662 %FAdd = fadd float %Cast.1, %Cast.2 \n\
663 %Add.3 = add i32 %L.2, %L.1 \n\
664 %Cast.3 = bitcast float %FAdd to i32 \n\
665 %Sub.2 = sub i32 %Cast.3, %Sub.1 \n\
666 %SExt = sext i32 %Cast.3 to i64 \n\
667 %A.GEP.3 = getelementptr i64, ptr %A, i32 1 \n\
668 store i64 %SExt, ptr %A.GEP.3 \n\
669 br label %Exit \n\
670 BB1: \n\
671 %PHI.1 = phi i32 [0, %Entry] \n\
672 %SExt.1 = sext i1 %Cond.2 to i32 \n\
673 %SExt.2 = sext i1 %Cond.1 to i32 \n\
674 %E.164 = zext i32 %E.1 to i64 \n\
675 %E.264 = zext i32 %E.2 to i64 \n\
676 %E.1264 = mul i64 %E.164, %E.264 \n\
677 %E.12 = trunc i64 %E.1264 to i32 \n\
678 %A.GEP.4 = getelementptr i32, ptr %A, i32 2 \n\
679 %A.GEP.5 = getelementptr i32, ptr %A.GEP.4, i32 2 \n\
680 store i32 %E.12, ptr %A.GEP.5 \n\
681 br label %Exit \n\
682 Exit: \n\
683 %PHI.2 = phi i32 [%Add, %BB0], [%E.3, %BB1] \n\
684 %PHI.3 = phi i64 [%SExt, %BB0], [%E.1264, %BB1] \n\
685 %ZExt = zext i32 %PHI.2 to i64 \n\
686 %Add.5 = add i64 %PHI.3, 3 \n\
687 ret i64 %Add.5 \n\
688 }";
689 VerifyBlockShuffle(Source);
690 }
691
TEST(ShuffleBlockStrategy,ShuffleLoop)692 TEST(ShuffleBlockStrategy, ShuffleLoop) {
693 StringRef Source = "\n\
694 define i32 @foo(i32 %Left, i32 %Right) { \n\
695 Entry: \n\
696 %LPtr = alloca i32, align 4 \n\
697 %RPtr = alloca i32, align 4 \n\
698 %RetValPtr = alloca i32, align 4 \n\
699 store i32 %Left, ptr %LPtr, align 4 \n\
700 store i32 %Right, ptr %RPtr, align 4 \n\
701 store i32 0, ptr %RetValPtr, align 4 \n\
702 br label %LoopHead \n\
703 LoopHead: \n\
704 %L = load i32, ptr %LPtr, align 4 \n\
705 %R = load i32, ptr %RPtr, align 4 \n\
706 %C = icmp slt i32 %L, %R \n\
707 br i1 %C, label %LoopBody, label %Exit \n\
708 LoopBody: \n\
709 %OldL = load i32, ptr %LPtr, align 4 \n\
710 %NewL = add nsw i32 %OldL, 1 \n\
711 store i32 %NewL, ptr %LPtr, align 4 \n\
712 %OldRetVal = load i32, ptr %RetValPtr, align 4 \n\
713 %NewRetVal = add nsw i32 %OldRetVal, 1 \n\
714 store i32 %NewRetVal, ptr %RetValPtr, align 4 \n\
715 br label %LoopHead \n\
716 Exit: \n\
717 %RetVal = load i32, ptr %RetValPtr, align 4 \n\
718 ret i32 %RetVal \n\
719 }";
720 VerifyBlockShuffle(Source);
721 }
722
TEST(AllStrategies,SkipEHPad)723 TEST(AllStrategies, SkipEHPad) {
724 StringRef Source = "\n\
725 define void @f(i32 %x) personality ptr @__CxxFrameHandler3 { \n\
726 entry: \n\
727 invoke void @g() to label %try.cont unwind label %catch.dispatch \n\
728 catch.dispatch: \n\
729 %0 = catchswitch within none [label %catch] unwind to caller \n\
730 catch: \n\
731 %1 = catchpad within %0 [ptr null, i32 64, ptr null] \n\
732 catchret from %1 to label %try.cont \n\
733 try.cont: \n\
734 ret void \n\
735 } \n\
736 declare void @g() \n\
737 declare i32 @__CxxFrameHandler3(...) \n\
738 ";
739
740 mutateAndVerifyModule<ShuffleBlockStrategy>(Source);
741 mutateAndVerifyModule<InsertPHIStrategy>(Source);
742 mutateAndVerifyModule<InsertFunctionStrategy>(Source);
743 mutateAndVerifyModule<InsertCFGStrategy>(Source);
744 mutateAndVerifyModule<SinkInstructionStrategy>(Source);
745 mutateAndVerifyModule<InjectorIRStrategy>(Source);
746 mutateAndVerifyModule<InstModificationIRStrategy>(Source);
747 }
748 } // namespace
749