llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp

   1 //===- RandomIRBuilderTest.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/FuzzMutate/RandomIRBuilder.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/OpDescriptor.h"
  15 #include "llvm/FuzzMutate/Operations.h"
  16 #include "llvm/FuzzMutate/Random.h"
  17 #include "llvm/IR/Constants.h"
  18 #include "llvm/IR/Dominators.h"
  19 #include "llvm/IR/Instructions.h"
  20 #include "llvm/IR/LLVMContext.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/IR/Verifier.h"
  23 #include "llvm/Support/SourceMgr.h"
  24
  25 #include "gtest/gtest.h"
  26
  27 using namespace llvm;
  28
  29 static constexpr int Seed = 5;
  30
  31 namespace {
  32
  33 std::unique_ptr<Module> parseAssembly(const char *Assembly,
  34                                       LLVMContext &Context) {
  35
  36   SMDiagnostic Error;
  37   std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
  38
  39   std::string ErrMsg;
  40   raw_string_ostream OS(ErrMsg);
  41   Error.print("", OS);
  42
  43   assert(M && !verifyModule(*M, &errs()));
  44   return M;
  45 }
  46
  47 TEST(RandomIRBuilderTest, ShuffleVectorIncorrectOperands) {
  48   // Test that we don't create load instruction as a source for the shuffle
  49   // vector operation.
  50
  51   LLVMContext Ctx;
  52   const char *Source =
  53       "define <2 x i32> @test(<2 x i1> %cond, <2 x i32> %a) {\n"
  54       "  %A = alloca <2 x i32>\n"
  55       "  %I = insertelement <2 x i32> %a, i32 1, i32 1\n"
  56       "  ret <2 x i32> undef\n"
  57       "}";
  58   auto M = parseAssembly(Source, Ctx);
  59
  60   fuzzerop::OpDescriptor Descr = fuzzerop::shuffleVectorDescriptor(1);
  61
  62   // Empty known types since we ShuffleVector descriptor doesn't care about them
  63   RandomIRBuilder IB(Seed, {});
  64
  65   // Get first basic block of the first function
  66   Function &F = *M->begin();
  67   BasicBlock &BB = *F.begin();
  68
  69   SmallVector<Instruction *, 32> Insts;
  70   for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
  71     Insts.push_back(&*I);
  72
  73   // Pick first and second sources
  74   SmallVector<Value *, 2> Srcs;
  75   ASSERT_TRUE(Descr.SourcePreds[0].matches(Srcs, Insts[1]));
  76   Srcs.push_back(Insts[1]);
  77   ASSERT_TRUE(Descr.SourcePreds[1].matches(Srcs, Insts[1]));
  78   Srcs.push_back(Insts[1]);
  79
  80   // Create new source. Check that it always matches with the descriptor.
  81   // Run some iterations to account for random decisions.
  82   for (int i = 0; i < 10; ++i) {
  83     Value *LastSrc = IB.newSource(BB, Insts, Srcs, Descr.SourcePreds[2]);
  84     ASSERT_TRUE(Descr.SourcePreds[2].matches(Srcs, LastSrc));
  85   }
  86 }
  87
  88 TEST(RandomIRBuilderTest, InsertValueIndexes) {
  89   // Check that we will generate correct indexes for the insertvalue operation
  90
  91   LLVMContext Ctx;
  92   const char *Source = "%T = type {i8, i32, i64}\n"
  93                        "define void @test() {\n"
  94                        "  %A = alloca %T\n"
  95                        "  %L = load %T, ptr %A"
  96                        "  ret void\n"
  97                        "}";
  98   auto M = parseAssembly(Source, Ctx);
  99
 100   fuzzerop::OpDescriptor IVDescr = fuzzerop::insertValueDescriptor(1);
 101
 102   std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
 103                                  Type::getInt64Ty(Ctx)};
 104   RandomIRBuilder IB(Seed, Types);
 105
 106   // Get first basic block of the first function
 107   Function &F = *M->begin();
 108   BasicBlock &BB = *F.begin();
 109
 110   // Pick first source
 111   Instruction *Src = &*std::next(BB.begin());
 112
 113   SmallVector<Value *, 2> Srcs(2);
 114   ASSERT_TRUE(IVDescr.SourcePreds[0].matches({}, Src));
 115   Srcs[0] = Src;
 116
 117   // Generate constants for each of the types and check that we pick correct
 118   // index for the given type
 119   for (auto *T : Types) {
 120     // Loop to account for possible random decisions
 121     for (int i = 0; i < 10; ++i) {
 122       // Create value we want to insert. Only it's type matters.
 123       Srcs[1] = ConstantInt::get(T, 5);
 124
 125       // Try to pick correct index
 126       Value *Src =
 127           IB.findOrCreateSource(BB, &*BB.begin(), Srcs, IVDescr.SourcePreds[2]);
 128       ASSERT_TRUE(IVDescr.SourcePreds[2].matches(Srcs, Src));
 129     }
 130   }
 131 }
 132
 133 TEST(RandomIRBuilderTest, ShuffleVectorSink) {
 134   // Check that we will never use shuffle vector mask as a sink from the
 135   // unrelated operation.
 136
 137   LLVMContext Ctx;
 138   const char *SourceCode =
 139       "define void @test(<4 x i32> %a) {\n"
 140       "  %S1 = shufflevector <4 x i32> %a, <4 x i32> %a, <4 x i32> undef\n"
 141       "  %S2 = shufflevector <4 x i32> %a, <4 x i32> %a, <4 x i32> undef\n"
 142       "  ret void\n"
 143       "}";
 144   auto M = parseAssembly(SourceCode, Ctx);
 145
 146   fuzzerop::OpDescriptor IVDescr = fuzzerop::insertValueDescriptor(1);
 147
 148   RandomIRBuilder IB(Seed, {});
 149
 150   // Get first basic block of the first function
 151   Function &F = *M->begin();
 152   BasicBlock &BB = *F.begin();
 153
 154   // Source is %S1
 155   Instruction *Source = &*BB.begin();
 156   // Sink is %S2
 157   SmallVector<Instruction *, 1> Sinks = {&*std::next(BB.begin())};
 158
 159   // Loop to account for random decisions
 160   for (int i = 0; i < 10; ++i) {
 161     // Try to connect S1 to S2. We should always create new sink.
 162     IB.connectToSink(BB, Sinks, Source);
 163     ASSERT_TRUE(!verifyModule(*M, &errs()));
 164   }
 165 }
 166
 167 TEST(RandomIRBuilderTest, InsertValueArray) {
 168   // Check that we can generate insertvalue for the vector operations
 169
 170   LLVMContext Ctx;
 171   const char *SourceCode = "define void @test() {\n"
 172                            "  %A = alloca [8 x i32]\n"
 173                            "  %L = load [8 x i32], ptr %A"
 174                            "  ret void\n"
 175                            "}";
 176   auto M = parseAssembly(SourceCode, Ctx);
 177
 178   fuzzerop::OpDescriptor Descr = fuzzerop::insertValueDescriptor(1);
 179
 180   std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
 181                                  Type::getInt64Ty(Ctx)};
 182   RandomIRBuilder IB(Seed, Types);
 183
 184   // Get first basic block of the first function
 185   Function &F = *M->begin();
 186   BasicBlock &BB = *F.begin();
 187
 188   // Pick first source
 189   Instruction *Source = &*std::next(BB.begin());
 190   ASSERT_TRUE(Descr.SourcePreds[0].matches({}, Source));
 191
 192   SmallVector<Value *, 2> Srcs(2);
 193
 194   // Check that we can always pick the last two operands.
 195   for (int i = 0; i < 10; ++i) {
 196     Srcs[0] = Source;
 197     Srcs[1] = IB.findOrCreateSource(BB, {Source}, Srcs, Descr.SourcePreds[1]);
 198     IB.findOrCreateSource(BB, {}, Srcs, Descr.SourcePreds[2]);
 199   }
 200 }
 201
 202 TEST(RandomIRBuilderTest, Invokes) {
 203   // Check that we never generate load or store after invoke instruction
 204
 205   LLVMContext Ctx;
 206   const char *SourceCode =
 207       "declare ptr @f()"
 208       "declare i32 @personality_function()"
 209       "define ptr @test() personality ptr @personality_function {\n"
 210       "entry:\n"
 211       "  %val = invoke ptr @f()\n"
 212       "          to label %normal unwind label %exceptional\n"
 213       "normal:\n"
 214       "  ret ptr %val\n"
 215       "exceptional:\n"
 216       "  %landing_pad4 = landingpad token cleanup\n"
 217       "  ret ptr undef\n"
 218       "}";
 219   auto M = parseAssembly(SourceCode, Ctx);
 220
 221   std::array<Type *, 1> Types = {Type::getInt8Ty(Ctx)};
 222   RandomIRBuilder IB(Seed, Types);
 223
 224   // Get first basic block of the test function
 225   Function &F = *M->getFunction("test");
 226   BasicBlock &BB = *F.begin();
 227
 228   Instruction *Invoke = &*BB.begin();
 229
 230   // Find source but never insert new load after invoke
 231   for (int i = 0; i < 10; ++i) {
 232     (void)IB.findOrCreateSource(BB, {Invoke}, {}, fuzzerop::anyIntType());
 233     ASSERT_TRUE(!verifyModule(*M, &errs()));
 234   }
 235 }
 236
 237 TEST(RandomIRBuilderTest, SwiftError) {
 238   // Check that we never pick swifterror value as a source for operation
 239   // other than load, store and call.
 240
 241   LLVMContext Ctx;
 242   const char *SourceCode = "declare void @use(ptr swifterror %err)"
 243                            "define void @test() {\n"
 244                            "entry:\n"
 245                            "  %err = alloca swifterror ptr, align 8\n"
 246                            "  call void @use(ptr swifterror %err)\n"
 247                            "  ret void\n"
 248                            "}";
 249   auto M = parseAssembly(SourceCode, Ctx);
 250
 251   std::array<Type *, 1> Types = {Type::getInt8Ty(Ctx)};
 252   RandomIRBuilder IB(Seed, Types);
 253
 254   // Get first basic block of the test function
 255   Function &F = *M->getFunction("test");
 256   BasicBlock &BB = *F.begin();
 257   Instruction *Alloca = &*BB.begin();
 258
 259   fuzzerop::OpDescriptor Descr = fuzzerop::gepDescriptor(1);
 260
 261   for (int i = 0; i < 10; ++i) {
 262     Value *V = IB.findOrCreateSource(BB, {Alloca}, {}, Descr.SourcePreds[0]);
 263     ASSERT_FALSE(isa<AllocaInst>(V));
 264   }
 265 }
 266
 267 TEST(RandomIRBuilderTest, dontConnectToSwitch) {
 268   // Check that we never put anything into switch's case branch
 269   // If we accidently put a variable, the module is invalid.
 270   LLVMContext Ctx;
 271   const char *SourceCode = "\n\
 272     define void @test(i1 %C1, i1 %C2, i32 %I, i32 %J) { \n\
 273     Entry:  \n\
 274       %I.1 = add i32 %I, 42 \n\
 275       %J.1 = add i32 %J, 42 \n\
 276       %IJ = add i32 %I, %J \n\
 277       switch i32 %I, label %Default [ \n\
 278         i32 1, label %OnOne  \n\
 279       ] \n\
 280     Default:  \n\
 281       %CIEqJ = icmp eq i32 %I.1, %J.1 \n\
 282       %CISltJ = icmp slt i32 %I.1, %J.1 \n\
 283       %CAnd = and i1 %C1, %C2 \n\
 284       br i1 %CIEqJ, label %Default, label %Exit \n\
 285     OnOne:  \n\
 286       br i1 %C1, label %OnOne, label %Exit \n\
 287     Exit:  \n\
 288       ret void \n\
 289     }";
 290
 291   std::array<Type *, 2> Types = {Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)};
 292   RandomIRBuilder IB(Seed, Types);
 293   for (int i = 0; i < 20; i++) {
 294     std::unique_ptr<Module> M = parseAssembly(SourceCode, Ctx);
 295     Function &F = *M->getFunction("test");
 296     auto RS = makeSampler(IB.Rand, make_pointer_range(F));
 297     BasicBlock *BB = RS.getSelection();
 298     SmallVector<Instruction *, 32> Insts;
 299     for (auto I = BB->getFirstInsertionPt(), E = BB->end(); I != E; ++I)
 300       Insts.push_back(&*I);
 301     if (Insts.size() < 2)
 302       continue;
 303     // Choose an instruction and connect to later operations.
 304     size_t IP = uniform<size_t>(IB.Rand, 1, Insts.size() - 1);
 305     Instruction *Inst = Insts[IP - 1];
 306     auto ConnectAfter = ArrayRef(Insts).slice(IP);
 307     IB.connectToSink(*BB, ConnectAfter, Inst);
 308     ASSERT_FALSE(verifyModule(*M, &errs()));
 309   }
 310 }
 311
 312 TEST(RandomIRBuilderTest, createStackMemory) {
 313   LLVMContext Ctx;
 314   const char *SourceCode = "\n\
 315     define void @test(i1 %C1, i1 %C2, i32 %I, i32 %J) { \n\
 316     Entry:  \n\
 317       ret void \n\
 318     }";
 319   Type *Int32Ty = Type::getInt32Ty(Ctx);
 320   Constant *Int32_1 = ConstantInt::get(Int32Ty, APInt(32, 1));
 321   Type *Int64Ty = Type::getInt64Ty(Ctx);
 322   Constant *Int64_42 = ConstantInt::get(Int64Ty, APInt(64, 42));
 323   Type *DoubleTy = Type::getDoubleTy(Ctx);
 324   Constant *Double_0 =
 325       ConstantFP::get(Ctx, APFloat::getZero(DoubleTy->getFltSemantics()));
 326   std::array<Type *, 8> Types = {
 327       Int32Ty,
 328       Int64Ty,
 329       DoubleTy,
 330       PointerType::get(Ctx, 0),
 331       PointerType::get(Int32Ty, 0),
 332       VectorType::get(Int32Ty, 4, false),
 333       StructType::create({Int32Ty, DoubleTy, Int64Ty}),
 334       ArrayType::get(Int64Ty, 4),
 335   };
 336   std::array<Value *, 8> Inits = {
 337       Int32_1,
 338       Int64_42,
 339       Double_0,
 340       UndefValue::get(Types[3]),
 341       UndefValue::get(Types[4]),
 342       ConstantVector::get({Int32_1, Int32_1, Int32_1, Int32_1}),
 343       ConstantStruct::get(cast<StructType>(Types[6]),
 344                           {Int32_1, Double_0, Int64_42}),
 345       ConstantArray::get(cast<ArrayType>(Types[7]),
 346                          {Int64_42, Int64_42, Int64_42, Int64_42}),
 347   };
 348   ASSERT_EQ(Types.size(), Inits.size());
 349   unsigned NumTests = Types.size();
 350   RandomIRBuilder IB(Seed, Types);
 351   auto CreateStackMemoryAndVerify = [&Ctx, &SourceCode, &IB](Type *Ty,
 352                                                              Value *Init) {
 353     std::unique_ptr<Module> M = parseAssembly(SourceCode, Ctx);
 354     Function &F = *M->getFunction("test");
 355     // Create stack memory without initializer.
 356     IB.createStackMemory(&F, Ty, nullptr);
 357     // Create stack memory with initializer.
 358     IB.createStackMemory(&F, Ty, Init);
 359     EXPECT_FALSE(verifyModule(*M, &errs()));
 360   };
 361   for (unsigned i = 0; i < NumTests; i++) {
 362     CreateStackMemoryAndVerify(Types[i], Inits[i]);
 363   }
 364 }
 365
 366 TEST(RandomIRBuilderTest, findOrCreateGlobalVariable) {
 367   LLVMContext Ctx;
 368   const char *SourceCode = "\n\
 369     @G0 = external global i16 \n\
 370     @G1 = global i32 1 \n\
 371   ";
 372   std::array<Type *, 3> Types = {Type::getInt16Ty(Ctx), Type::getInt32Ty(Ctx),
 373                                  Type::getInt64Ty(Ctx)};
 374   RandomIRBuilder IB(Seed, Types);
 375
 376   // Find external global
 377   std::unique_ptr<Module> M0 = parseAssembly(SourceCode, Ctx);
 378   Type *ExternalTy = M0->globals().begin()->getValueType();
 379   ASSERT_TRUE(ExternalTy->isIntegerTy(16));
 380   IB.findOrCreateGlobalVariable(&*M0, {}, fuzzerop::onlyType(Types[0]));
 381   ASSERT_FALSE(verifyModule(*M0, &errs()));
 382   unsigned NumGV0 = M0->getNumNamedValues();
 383   auto [GV0, DidCreate0] =
 384       IB.findOrCreateGlobalVariable(&*M0, {}, fuzzerop::onlyType(Types[0]));
 385   ASSERT_FALSE(verifyModule(*M0, &errs()));
 386   ASSERT_EQ(M0->getNumNamedValues(), NumGV0 + DidCreate0);
 387
 388   // Find existing global
 389   std::unique_ptr<Module> M1 = parseAssembly(SourceCode, Ctx);
 390   IB.findOrCreateGlobalVariable(&*M1, {}, fuzzerop::onlyType(Types[1]));
 391   ASSERT_FALSE(verifyModule(*M1, &errs()));
 392   unsigned NumGV1 = M1->getNumNamedValues();
 393   auto [GV1, DidCreate1] =
 394       IB.findOrCreateGlobalVariable(&*M1, {}, fuzzerop::onlyType(Types[1]));
 395   ASSERT_FALSE(verifyModule(*M1, &errs()));
 396   ASSERT_EQ(M1->getNumNamedValues(), NumGV1 + DidCreate1);
 397
 398   // Create new global
 399   std::unique_ptr<Module> M2 = parseAssembly(SourceCode, Ctx);
 400   auto [GV2, DidCreate2] =
 401       IB.findOrCreateGlobalVariable(&*M2, {}, fuzzerop::onlyType(Types[2]));
 402   ASSERT_FALSE(verifyModule(*M2, &errs()));
 403   ASSERT_TRUE(DidCreate2);
 404 }
 405
 406 /// Checks if the source and sink we find for an instruction has correct
 407 /// domination relation.
 408 TEST(RandomIRBuilderTest, findSourceAndSink) {
 409   const char *Source = "\n\
 410         define i64 @test(i1 %0, i1 %1, i1 %2, i32 %3, i32 %4) { \n\
 411         Entry:  \n\
 412           %A = alloca i32, i32 8, align 4 \n\
 413           %E.1 = and i32 %3, %4 \n\
 414           %E.2 = add i32 %4 , 1 \n\
 415           %A.GEP.1 = getelementptr i32, ptr %A, i32 0 \n\
 416           %A.GEP.2 = getelementptr i32, ptr %A.GEP.1, i32 1 \n\
 417           %L.2 = load i32, ptr %A.GEP.2 \n\
 418           %L.1 = load i32, ptr %A.GEP.1 \n\
 419           %E.3 = sub i32 %E.2, %L.1 \n\
 420           %Cond.1 = icmp eq i32 %E.3, %E.2 \n\
 421           %Cond.2 = and i1 %0, %1 \n\
 422           %Cond = or i1 %Cond.1, %Cond.2 \n\
 423           br i1 %Cond, label %BB0, label %BB1  \n\
 424         BB0:  \n\
 425           %Add = add i32 %L.1, %L.2 \n\
 426           %Sub = sub i32 %L.1, %L.2 \n\
 427           %Sub.1 = sub i32 %Sub, 12 \n\
 428           %Cast.1 = bitcast i32 %4 to float \n\
 429           %Add.2 = add i32 %3, 1 \n\
 430           %Cast.2 = bitcast i32 %Add.2 to float \n\
 431           %FAdd = fadd float %Cast.1, %Cast.2 \n\
 432           %Add.3 = add i32 %L.2, %L.1 \n\
 433           %Cast.3 = bitcast float %FAdd to i32 \n\
 434           %Sub.2 = sub i32 %Cast.3, %Sub.1 \n\
 435           %SExt = sext i32 %Cast.3 to i64 \n\
 436           %A.GEP.3 = getelementptr i64, ptr %A, i32 1 \n\
 437           store i64 %SExt, ptr %A.GEP.3 \n\
 438           br label %Exit  \n\
 439         BB1:  \n\
 440           %PHI.1 = phi i32 [0, %Entry] \n\
 441           %SExt.1 = sext i1 %Cond.2 to i32 \n\
 442           %SExt.2 = sext i1 %Cond.1 to i32 \n\
 443           %E.164 = zext i32 %E.1 to i64 \n\
 444           %E.264 = zext i32 %E.2 to i64 \n\
 445           %E.1264 = mul i64 %E.164, %E.264 \n\
 446           %E.12 = trunc i64 %E.1264 to i32 \n\
 447           %A.GEP.4 = getelementptr i32, ptr %A, i32 2 \n\
 448           %A.GEP.5 = getelementptr i32, ptr %A.GEP.4, i32 2 \n\
 449           store i32 %E.12, ptr %A.GEP.5 \n\
 450           br label %Exit  \n\
 451         Exit:  \n\
 452           %PHI.2 = phi i32 [%Add, %BB0], [%E.3, %BB1] \n\
 453           %PHI.3 = phi i64 [%SExt, %BB0], [%E.1264, %BB1] \n\
 454           %ZExt = zext i32 %PHI.2 to i64 \n\
 455           %Add.5 = add i64 %PHI.3, 3 \n\
 456           ret i64 %Add.5  \n\
 457       }";
 458   LLVMContext Ctx;
 459   std::array<Type *, 3> Types = {Type::getInt1Ty(Ctx), Type::getInt32Ty(Ctx),
 460                                  Type::getInt64Ty(Ctx)};
 461   std::mt19937 mt(Seed);
 462   std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
 463
 464   // Get a random instruction, try to find source and sink, make sure it is
 465   // dominated.
 466   for (int i = 0; i < 100; i++) {
 467     RandomIRBuilder IB(RandInt(mt), Types);
 468     std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
 469     Function &F = *M->getFunction("test");
 470     DominatorTree DT(F);
 471     BasicBlock *BB = makeSampler(IB.Rand, make_pointer_range(F)).getSelection();
 472     SmallVector<Instruction *, 32> Insts;
 473     for (auto I = BB->getFirstInsertionPt(), E = BB->end(); I != E; ++I)
 474       Insts.push_back(&*I);
 475     // Choose an insertion point for our new instruction.
 476     size_t IP = uniform<size_t>(IB.Rand, 1, Insts.size() - 2);
 477
 478     auto InstsBefore = ArrayRef(Insts).slice(0, IP);
 479     auto InstsAfter = ArrayRef(Insts).slice(IP);
 480     Value *Src = IB.findOrCreateSource(
 481         *BB, InstsBefore, {}, fuzzerop::onlyType(Types[i % Types.size()]));
 482     ASSERT_TRUE(DT.dominates(Src, Insts[IP + 1]));
 483     Instruction *Sink = IB.connectToSink(*BB, InstsAfter, Insts[IP - 1]);
 484     if (!DT.dominates(Insts[IP - 1], Sink)) {
 485       errs() << *Insts[IP - 1] << "\n" << *Sink << "\n ";
 486     }
 487     ASSERT_TRUE(DT.dominates(Insts[IP - 1], Sink));
 488   }
 489 }
 490 TEST(RandomIRBuilderTest, sinkToIntrinsic) {
 491   const char *Source = "\n\
 492         declare double @llvm.sqrt.f64(double %Val)  \n\
 493         declare void   @llvm.ubsantrap(i8 immarg) cold noreturn nounwind  \n\
 494         \n\
 495         define double @test(double %0, double %1, i64 %2, i64 %3, i64 %4, i8 %5) {  \n\
 496         Entry:   \n\
 497             %sqrt = call double @llvm.sqrt.f64(double %0)  \n\
 498             call void @llvm.ubsantrap(i8 1)  \n\
 499             ret double %sqrt \n\
 500         }";
 501   LLVMContext Ctx;
 502   std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt64Ty(Ctx),
 503                                  Type::getDoubleTy(Ctx)};
 504   std::mt19937 mt(Seed);
 505   std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
 506
 507   RandomIRBuilder IB(RandInt(mt), Types);
 508   std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
 509   Function &F = *M->getFunction("test");
 510   BasicBlock &BB = F.getEntryBlock();
 511   bool Modified = false;
 512
 513   Instruction *I = &*BB.begin();
 514   for (int i = 0; i < 20; i++) {
 515     Value *OldOperand = I->getOperand(0);
 516     Value *Src = F.getArg(1);
 517     IB.connectToSink(BB, {I}, Src);
 518     Value *NewOperand = I->getOperand(0);
 519     Modified |= (OldOperand != NewOperand);
 520     ASSERT_FALSE(verifyModule(*M, &errs()));
 521   }
 522   ASSERT_TRUE(Modified);
 523
 524   Modified = false;
 525   I = I->getNextNonDebugInstruction();
 526   for (int i = 0; i < 20; i++) {
 527     Value *OldOperand = I->getOperand(0);
 528     Value *Src = F.getArg(5);
 529     IB.connectToSink(BB, {I}, Src);
 530     Value *NewOperand = I->getOperand(0);
 531     Modified |= (OldOperand != NewOperand);
 532     ASSERT_FALSE(verifyModule(*M, &errs()));
 533   }
 534   ASSERT_FALSE(Modified);
 535 }
 536
 537 TEST(RandomIRBuilderTest, DoNotCallPointerWhenSink) {
 538   const char *Source = "\n\
 539         declare void @g()  \n\
 540         define void @f(ptr %ptr) {  \n\
 541         Entry:   \n\
 542             call void @g()  \n\
 543             ret void \n\
 544         }";
 545   LLVMContext Ctx;
 546   std::mt19937 mt(Seed);
 547   std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
 548
 549   RandomIRBuilder IB(RandInt(mt), {});
 550   std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
 551   Function &F = *M->getFunction("f");
 552   BasicBlock &BB = F.getEntryBlock();
 553   bool Modified = false;
 554
 555   Instruction *I = &*BB.begin();
 556   for (int i = 0; i < 20; i++) {
 557     Value *OldOperand = I->getOperand(0);
 558     Value *Src = F.getArg(0);
 559     IB.connectToSink(BB, {I}, Src);
 560     Value *NewOperand = I->getOperand(0);
 561     Modified |= (OldOperand != NewOperand);
 562     ASSERT_FALSE(verifyModule(*M, &errs()));
 563   }
 564   ASSERT_FALSE(Modified);
 565 }
 566
 567 TEST(RandomIRBuilderTest, SrcAndSinkWOrphanBlock) {
 568   const char *Source = "\n\
 569         define i1 @test(i1 %Bool, i32 %Int, i64 %Long) {   \n\
 570         Entry:    \n\
 571             %Eq0 = icmp eq i64 %Long, 0 \n\
 572             br i1 %Eq0, label %True, label %False \n\
 573         True: \n\
 574             %Or = or i1 %Bool, %Eq0 \n\
 575             ret i1 %Or \n\
 576         False: \n\
 577             %And = and i1 %Bool, %Eq0 \n\
 578             ret i1 %And \n\
 579         Orphan_1:  \n\
 580             %NotBool = sub i1 1, %Bool \n\
 581             ret i1 %NotBool \n\
 582         Orphan_2:  \n\
 583             %Le42 = icmp sle i32 %Int, 42 \n\
 584             ret i1 %Le42 \n\
 585         }";
 586   LLVMContext Ctx;
 587   std::mt19937 mt(Seed);
 588   std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
 589   std::array<Type *, 3> IntTys(
 590       {Type::getInt64Ty(Ctx), Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)});
 591   std::vector<Value *> Constants;
 592   for (Type *IntTy : IntTys) {
 593     for (size_t v : {1, 42}) {
 594       Constants.push_back(ConstantInt::get(IntTy, v));
 595     }
 596   }
 597   for (int i = 0; i < 10; i++) {
 598     RandomIRBuilder IB(RandInt(mt), IntTys);
 599     std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
 600     Function &F = *M->getFunction("test");
 601     for (BasicBlock &BB : F) {
 602       SmallVector<Instruction *, 4> Insts;
 603       for (Instruction &I : BB) {
 604         Insts.push_back(&I);
 605       }
 606       for (int j = 0; j < 10; j++) {
 607         IB.findOrCreateSource(BB, Insts);
 608       }
 609       for (Value *V : Constants) {
 610         IB.connectToSink(BB, Insts, V);
 611       }
 612     }
 613   }
 614 }
 615 } // namespace