//===- RandomIRBuilderTest.cpp - Tests for injector strategy --------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/FuzzMutate/RandomIRBuilder.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/AsmParser/SlotMapping.h"
#include "llvm/FuzzMutate/IRMutator.h"
#include "llvm/FuzzMutate/OpDescriptor.h"
#include "llvm/FuzzMutate/Operations.h"
#include "llvm/FuzzMutate/Random.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/SourceMgr.h"

#include "gtest/gtest.h"

using namespace llvm;

static constexpr int Seed = 5;

namespace {

std::unique_ptr<Module> parseAssembly(const char *Assembly,
                                      LLVMContext &Context) {

  SMDiagnostic Error;
  std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);

  std::string ErrMsg;
  raw_string_ostream OS(ErrMsg);
  Error.print("", OS);

  assert(M && !verifyModule(*M, &errs()));
  return M;
}

TEST(RandomIRBuilderTest, ShuffleVectorIncorrectOperands) {
  // Test that we don't create load instruction as a source for the shuffle
  // vector operation.

  LLVMContext Ctx;
  const char *Source =
      "define <2 x i32> @test(<2 x i1> %cond, <2 x i32> %a) {\n"
      "  %A = alloca <2 x i32>\n"
      "  %I = insertelement <2 x i32> %a, i32 1, i32 1\n"
      "  ret <2 x i32> undef\n"
      "}";
  auto M = parseAssembly(Source, Ctx);

  fuzzerop::OpDescriptor Descr = fuzzerop::shuffleVectorDescriptor(1);

  // Empty known types since we ShuffleVector descriptor doesn't care about them
  RandomIRBuilder IB(Seed, {});

  // Get first basic block of the first function
  Function &F = *M->begin();
  BasicBlock &BB = *F.begin();

  SmallVector<Instruction *, 32> Insts;
  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
    Insts.push_back(&*I);

  // Pick first and second sources
  SmallVector<Value *, 2> Srcs;
  ASSERT_TRUE(Descr.SourcePreds[0].matches(Srcs, Insts[1]));
  Srcs.push_back(Insts[1]);
  ASSERT_TRUE(Descr.SourcePreds[1].matches(Srcs, Insts[1]));
  Srcs.push_back(Insts[1]);

  // Create new source. Check that it always matches with the descriptor.
  // Run some iterations to account for random decisions.
  for (int i = 0; i < 10; ++i) {
    Value *LastSrc = IB.newSource(BB, Insts, Srcs, Descr.SourcePreds[2]);
    ASSERT_TRUE(Descr.SourcePreds[2].matches(Srcs, LastSrc));
  }
}

TEST(RandomIRBuilderTest, InsertValueIndexes) {
  // Check that we will generate correct indexes for the insertvalue operation

  LLVMContext Ctx;
  const char *Source = "%T = type {i8, i32, i64}\n"
                       "define void @test() {\n"
                       "  %A = alloca %T\n"
                       "  %L = load %T, ptr %A"
                       "  ret void\n"
                       "}";
  auto M = parseAssembly(Source, Ctx);

  fuzzerop::OpDescriptor IVDescr = fuzzerop::insertValueDescriptor(1);

  std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
                                 Type::getInt64Ty(Ctx)};
  RandomIRBuilder IB(Seed, Types);

  // Get first basic block of the first function
  Function &F = *M->begin();
  BasicBlock &BB = *F.begin();

  // Pick first source
  Instruction *Src = &*std::next(BB.begin());

  SmallVector<Value *, 2> Srcs(2);
  ASSERT_TRUE(IVDescr.SourcePreds[0].matches({}, Src));
  Srcs[0] = Src;

  // Generate constants for each of the types and check that we pick correct
  // index for the given type
  for (auto *T : Types) {
    // Loop to account for possible random decisions
    for (int i = 0; i < 10; ++i) {
      // Create value we want to insert. Only it's type matters.
      Srcs[1] = ConstantInt::get(T, 5);

      // Try to pick correct index
      Value *Src =
          IB.findOrCreateSource(BB, &*BB.begin(), Srcs, IVDescr.SourcePreds[2]);
      ASSERT_TRUE(IVDescr.SourcePreds[2].matches(Srcs, Src));
    }
  }
}

TEST(RandomIRBuilderTest, ShuffleVectorSink) {
  // Check that we will never use shuffle vector mask as a sink from the
  // unrelated operation.

  LLVMContext Ctx;
  const char *SourceCode =
      "define void @test(<4 x i32> %a) {\n"
      "  %S1 = shufflevector <4 x i32> %a, <4 x i32> %a, <4 x i32> undef\n"
      "  %S2 = shufflevector <4 x i32> %a, <4 x i32> %a, <4 x i32> undef\n"
      "  ret void\n"
      "}";
  auto M = parseAssembly(SourceCode, Ctx);

  fuzzerop::OpDescriptor IVDescr = fuzzerop::insertValueDescriptor(1);

  RandomIRBuilder IB(Seed, {});

  // Get first basic block of the first function
  Function &F = *M->begin();
  BasicBlock &BB = *F.begin();

  // Source is %S1
  Instruction *Source = &*BB.begin();
  // Sink is %S2
  SmallVector<Instruction *, 1> Sinks = {&*std::next(BB.begin())};

  // Loop to account for random decisions
  for (int i = 0; i < 10; ++i) {
    // Try to connect S1 to S2. We should always create new sink.
    IB.connectToSink(BB, Sinks, Source);
    ASSERT_TRUE(!verifyModule(*M, &errs()));
  }
}

TEST(RandomIRBuilderTest, InsertValueArray) {
  // Check that we can generate insertvalue for the vector operations

  LLVMContext Ctx;
  const char *SourceCode = "define void @test() {\n"
                           "  %A = alloca [8 x i32]\n"
                           "  %L = load [8 x i32], ptr %A"
                           "  ret void\n"
                           "}";
  auto M = parseAssembly(SourceCode, Ctx);

  fuzzerop::OpDescriptor Descr = fuzzerop::insertValueDescriptor(1);

  std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
                                 Type::getInt64Ty(Ctx)};
  RandomIRBuilder IB(Seed, Types);

  // Get first basic block of the first function
  Function &F = *M->begin();
  BasicBlock &BB = *F.begin();

  // Pick first source
  Instruction *Source = &*std::next(BB.begin());
  ASSERT_TRUE(Descr.SourcePreds[0].matches({}, Source));

  SmallVector<Value *, 2> Srcs(2);

  // Check that we can always pick the last two operands.
  for (int i = 0; i < 10; ++i) {
    Srcs[0] = Source;
    Srcs[1] = IB.findOrCreateSource(BB, {Source}, Srcs, Descr.SourcePreds[1]);
    IB.findOrCreateSource(BB, {}, Srcs, Descr.SourcePreds[2]);
  }
}

TEST(RandomIRBuilderTest, Invokes) {
  // Check that we never generate load or store after invoke instruction

  LLVMContext Ctx;
  const char *SourceCode =
      "declare ptr @f()"
      "declare i32 @personality_function()"
      "define ptr @test() personality ptr @personality_function {\n"
      "entry:\n"
      "  %val = invoke ptr @f()\n"
      "          to label %normal unwind label %exceptional\n"
      "normal:\n"
      "  ret ptr %val\n"
      "exceptional:\n"
      "  %landing_pad4 = landingpad token cleanup\n"
      "  ret ptr undef\n"
      "}";
  auto M = parseAssembly(SourceCode, Ctx);

  std::array<Type *, 1> Types = {Type::getInt8Ty(Ctx)};
  RandomIRBuilder IB(Seed, Types);

  // Get first basic block of the test function
  Function &F = *M->getFunction("test");
  BasicBlock &BB = *F.begin();

  Instruction *Invoke = &*BB.begin();

  // Find source but never insert new load after invoke
  for (int i = 0; i < 10; ++i) {
    (void)IB.findOrCreateSource(BB, {Invoke}, {}, fuzzerop::anyIntType());
    ASSERT_TRUE(!verifyModule(*M, &errs()));
  }
}

TEST(RandomIRBuilderTest, SwiftError) {
  // Check that we never pick swifterror value as a source for operation
  // other than load, store and call.

  LLVMContext Ctx;
  const char *SourceCode = "declare void @use(ptr swifterror %err)"
                           "define void @test() {\n"
                           "entry:\n"
                           "  %err = alloca swifterror ptr, align 8\n"
                           "  call void @use(ptr swifterror %err)\n"
                           "  ret void\n"
                           "}";
  auto M = parseAssembly(SourceCode, Ctx);

  std::array<Type *, 1> Types = {Type::getInt8Ty(Ctx)};
  RandomIRBuilder IB(Seed, Types);

  // Get first basic block of the test function
  Function &F = *M->getFunction("test");
  BasicBlock &BB = *F.begin();
  Instruction *Alloca = &*BB.begin();

  fuzzerop::OpDescriptor Descr = fuzzerop::gepDescriptor(1);

  for (int i = 0; i < 10; ++i) {
    Value *V = IB.findOrCreateSource(BB, {Alloca}, {}, Descr.SourcePreds[0]);
    ASSERT_FALSE(isa<AllocaInst>(V));
  }
}

TEST(RandomIRBuilderTest, dontConnectToSwitch) {
  // Check that we never put anything into switch's case branch
  // If we accidently put a variable, the module is invalid.
  LLVMContext Ctx;
  const char *SourceCode = "\n\
    define void @test(i1 %C1, i1 %C2, i32 %I, i32 %J) { \n\
    Entry:  \n\
      %I.1 = add i32 %I, 42 \n\
      %J.1 = add i32 %J, 42 \n\
      %IJ = add i32 %I, %J \n\
      switch i32 %I, label %Default [ \n\
        i32 1, label %OnOne  \n\
      ] \n\
    Default:  \n\
      %CIEqJ = icmp eq i32 %I.1, %J.1 \n\
      %CISltJ = icmp slt i32 %I.1, %J.1 \n\
      %CAnd = and i1 %C1, %C2 \n\
      br i1 %CIEqJ, label %Default, label %Exit \n\
    OnOne:  \n\
      br i1 %C1, label %OnOne, label %Exit \n\
    Exit:  \n\
      ret void \n\
    }";

  std::array<Type *, 2> Types = {Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)};
  RandomIRBuilder IB(Seed, Types);
  for (int i = 0; i < 20; i++) {
    std::unique_ptr<Module> M = parseAssembly(SourceCode, Ctx);
    Function &F = *M->getFunction("test");
    auto RS = makeSampler(IB.Rand, make_pointer_range(F));
    BasicBlock *BB = RS.getSelection();
    SmallVector<Instruction *, 32> Insts;
    for (auto I = BB->getFirstInsertionPt(), E = BB->end(); I != E; ++I)
      Insts.push_back(&*I);
    if (Insts.size() < 2)
      continue;
    // Choose an instruction and connect to later operations.
    size_t IP = uniform<size_t>(IB.Rand, 1, Insts.size() - 1);
    Instruction *Inst = Insts[IP - 1];
    auto ConnectAfter = ArrayRef(Insts).slice(IP);
    IB.connectToSink(*BB, ConnectAfter, Inst);
    ASSERT_FALSE(verifyModule(*M, &errs()));
  }
}

TEST(RandomIRBuilderTest, createStackMemory) {
  LLVMContext Ctx;
  const char *SourceCode = "\n\
    define void @test(i1 %C1, i1 %C2, i32 %I, i32 %J) { \n\
    Entry:  \n\
      ret void \n\
    }";
  Type *Int32Ty = Type::getInt32Ty(Ctx);
  Constant *Int32_1 = ConstantInt::get(Int32Ty, APInt(32, 1));
  Type *Int64Ty = Type::getInt64Ty(Ctx);
  Constant *Int64_42 = ConstantInt::get(Int64Ty, APInt(64, 42));
  Type *DoubleTy = Type::getDoubleTy(Ctx);
  Constant *Double_0 =
      ConstantFP::get(Ctx, APFloat::getZero(DoubleTy->getFltSemantics()));
  std::array<Type *, 8> Types = {
      Int32Ty,
      Int64Ty,
      DoubleTy,
      PointerType::get(Ctx, 0),
      PointerType::get(Int32Ty, 0),
      VectorType::get(Int32Ty, 4, false),
      StructType::create({Int32Ty, DoubleTy, Int64Ty}),
      ArrayType::get(Int64Ty, 4),
  };
  std::array<Value *, 8> Inits = {
      Int32_1,
      Int64_42,
      Double_0,
      UndefValue::get(Types[3]),
      UndefValue::get(Types[4]),
      ConstantVector::get({Int32_1, Int32_1, Int32_1, Int32_1}),
      ConstantStruct::get(cast<StructType>(Types[6]),
                          {Int32_1, Double_0, Int64_42}),
      ConstantArray::get(cast<ArrayType>(Types[7]),
                         {Int64_42, Int64_42, Int64_42, Int64_42}),
  };
  ASSERT_EQ(Types.size(), Inits.size());
  unsigned NumTests = Types.size();
  RandomIRBuilder IB(Seed, Types);
  auto CreateStackMemoryAndVerify = [&Ctx, &SourceCode, &IB](Type *Ty,
                                                             Value *Init) {
    std::unique_ptr<Module> M = parseAssembly(SourceCode, Ctx);
    Function &F = *M->getFunction("test");
    // Create stack memory without initializer.
    IB.createStackMemory(&F, Ty, nullptr);
    // Create stack memory with initializer.
    IB.createStackMemory(&F, Ty, Init);
    EXPECT_FALSE(verifyModule(*M, &errs()));
  };
  for (unsigned i = 0; i < NumTests; i++) {
    CreateStackMemoryAndVerify(Types[i], Inits[i]);
  }
}

TEST(RandomIRBuilderTest, findOrCreateGlobalVariable) {
  LLVMContext Ctx;
  const char *SourceCode = "\n\
    @G0 = external global i16 \n\
    @G1 = global i32 1 \n\
  ";
  std::array<Type *, 3> Types = {Type::getInt16Ty(Ctx), Type::getInt32Ty(Ctx),
                                 Type::getInt64Ty(Ctx)};
  RandomIRBuilder IB(Seed, Types);

  // Find external global
  std::unique_ptr<Module> M0 = parseAssembly(SourceCode, Ctx);
  Type *ExternalTy = M0->globals().begin()->getValueType();
  ASSERT_TRUE(ExternalTy->isIntegerTy(16));
  IB.findOrCreateGlobalVariable(&*M0, {}, fuzzerop::onlyType(Types[0]));
  ASSERT_FALSE(verifyModule(*M0, &errs()));
  unsigned NumGV0 = M0->getNumNamedValues();
  auto [GV0, DidCreate0] =
      IB.findOrCreateGlobalVariable(&*M0, {}, fuzzerop::onlyType(Types[0]));
  ASSERT_FALSE(verifyModule(*M0, &errs()));
  ASSERT_EQ(M0->getNumNamedValues(), NumGV0 + DidCreate0);

  // Find existing global
  std::unique_ptr<Module> M1 = parseAssembly(SourceCode, Ctx);
  IB.findOrCreateGlobalVariable(&*M1, {}, fuzzerop::onlyType(Types[1]));
  ASSERT_FALSE(verifyModule(*M1, &errs()));
  unsigned NumGV1 = M1->getNumNamedValues();
  auto [GV1, DidCreate1] =
      IB.findOrCreateGlobalVariable(&*M1, {}, fuzzerop::onlyType(Types[1]));
  ASSERT_FALSE(verifyModule(*M1, &errs()));
  ASSERT_EQ(M1->getNumNamedValues(), NumGV1 + DidCreate1);

  // Create new global
  std::unique_ptr<Module> M2 = parseAssembly(SourceCode, Ctx);
  auto [GV2, DidCreate2] =
      IB.findOrCreateGlobalVariable(&*M2, {}, fuzzerop::onlyType(Types[2]));
  ASSERT_FALSE(verifyModule(*M2, &errs()));
  ASSERT_TRUE(DidCreate2);
}

/// Checks if the source and sink we find for an instruction has correct
/// domination relation.
TEST(RandomIRBuilderTest, findSourceAndSink) {
  const char *Source = "\n\
        define i64 @test(i1 %0, i1 %1, i1 %2, i32 %3, i32 %4) { \n\
        Entry:  \n\
          %A = alloca i32, i32 8, align 4 \n\
          %E.1 = and i32 %3, %4 \n\
          %E.2 = add i32 %4 , 1 \n\
          %A.GEP.1 = getelementptr i32, ptr %A, i32 0 \n\
          %A.GEP.2 = getelementptr i32, ptr %A.GEP.1, i32 1 \n\
          %L.2 = load i32, ptr %A.GEP.2 \n\
          %L.1 = load i32, ptr %A.GEP.1 \n\
          %E.3 = sub i32 %E.2, %L.1 \n\
          %Cond.1 = icmp eq i32 %E.3, %E.2 \n\
          %Cond.2 = and i1 %0, %1 \n\
          %Cond = or i1 %Cond.1, %Cond.2 \n\
          br i1 %Cond, label %BB0, label %BB1  \n\
        BB0:  \n\
          %Add = add i32 %L.1, %L.2 \n\
          %Sub = sub i32 %L.1, %L.2 \n\
          %Sub.1 = sub i32 %Sub, 12 \n\
          %Cast.1 = bitcast i32 %4 to float \n\
          %Add.2 = add i32 %3, 1 \n\
          %Cast.2 = bitcast i32 %Add.2 to float \n\
          %FAdd = fadd float %Cast.1, %Cast.2 \n\
          %Add.3 = add i32 %L.2, %L.1 \n\
          %Cast.3 = bitcast float %FAdd to i32 \n\
          %Sub.2 = sub i32 %Cast.3, %Sub.1 \n\
          %SExt = sext i32 %Cast.3 to i64 \n\
          %A.GEP.3 = getelementptr i64, ptr %A, i32 1 \n\
          store i64 %SExt, ptr %A.GEP.3 \n\
          br label %Exit  \n\
        BB1:  \n\
          %PHI.1 = phi i32 [0, %Entry] \n\
          %SExt.1 = sext i1 %Cond.2 to i32 \n\
          %SExt.2 = sext i1 %Cond.1 to i32 \n\
          %E.164 = zext i32 %E.1 to i64 \n\
          %E.264 = zext i32 %E.2 to i64 \n\
          %E.1264 = mul i64 %E.164, %E.264 \n\
          %E.12 = trunc i64 %E.1264 to i32 \n\
          %A.GEP.4 = getelementptr i32, ptr %A, i32 2 \n\
          %A.GEP.5 = getelementptr i32, ptr %A.GEP.4, i32 2 \n\
          store i32 %E.12, ptr %A.GEP.5 \n\
          br label %Exit  \n\
        Exit:  \n\
          %PHI.2 = phi i32 [%Add, %BB0], [%E.3, %BB1] \n\
          %PHI.3 = phi i64 [%SExt, %BB0], [%E.1264, %BB1] \n\
          %ZExt = zext i32 %PHI.2 to i64 \n\
          %Add.5 = add i64 %PHI.3, 3 \n\
          ret i64 %Add.5  \n\
      }";
  LLVMContext Ctx;
  std::array<Type *, 3> Types = {Type::getInt1Ty(Ctx), Type::getInt32Ty(Ctx),
                                 Type::getInt64Ty(Ctx)};
  std::mt19937 mt(Seed);
  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);

  // Get a random instruction, try to find source and sink, make sure it is
  // dominated.
  for (int i = 0; i < 100; i++) {
    RandomIRBuilder IB(RandInt(mt), Types);
    std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
    Function &F = *M->getFunction("test");
    DominatorTree DT(F);
    BasicBlock *BB = makeSampler(IB.Rand, make_pointer_range(F)).getSelection();
    SmallVector<Instruction *, 32> Insts;
    for (auto I = BB->getFirstInsertionPt(), E = BB->end(); I != E; ++I)
      Insts.push_back(&*I);
    // Choose an insertion point for our new instruction.
    size_t IP = uniform<size_t>(IB.Rand, 1, Insts.size() - 2);

    auto InstsBefore = ArrayRef(Insts).slice(0, IP);
    auto InstsAfter = ArrayRef(Insts).slice(IP);
    Value *Src = IB.findOrCreateSource(
        *BB, InstsBefore, {}, fuzzerop::onlyType(Types[i % Types.size()]));
    ASSERT_TRUE(DT.dominates(Src, Insts[IP + 1]));
    Instruction *Sink = IB.connectToSink(*BB, InstsAfter, Insts[IP - 1]);
    if (!DT.dominates(Insts[IP - 1], Sink)) {
      errs() << *Insts[IP - 1] << "\n" << *Sink << "\n ";
    }
    ASSERT_TRUE(DT.dominates(Insts[IP - 1], Sink));
  }
}
TEST(RandomIRBuilderTest, sinkToInstrinsic) {
  const char *Source = "\n\
        declare double @llvm.sqrt.f64(double %Val)  \n\
        declare void   @llvm.ubsantrap(i8 immarg) cold noreturn nounwind  \n\
        \n\
        define double @test(double %0, double %1, i64 %2, i64 %3, i64 %4, i8 %5) {  \n\
        Entry:   \n\
            %sqrt = call double @llvm.sqrt.f64(double %0)  \n\
            call void @llvm.ubsantrap(i8 1)  \n\
            ret double %sqrt \n\
        }";
  LLVMContext Ctx;
  std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt64Ty(Ctx),
                                 Type::getDoubleTy(Ctx)};
  std::mt19937 mt(Seed);
  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);

  RandomIRBuilder IB(RandInt(mt), Types);
  std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
  Function &F = *M->getFunction("test");
  BasicBlock &BB = F.getEntryBlock();
  bool Modified = false;

  Instruction *I = &*BB.begin();
  for (int i = 0; i < 20; i++) {
    Value *OldOperand = I->getOperand(0);
    Value *Src = F.getArg(1);
    IB.connectToSink(BB, {I}, Src);
    Value *NewOperand = I->getOperand(0);
    Modified |= (OldOperand != NewOperand);
    ASSERT_FALSE(verifyModule(*M, &errs()));
  }
  ASSERT_TRUE(Modified);

  Modified = false;
  I = I->getNextNonDebugInstruction();
  for (int i = 0; i < 20; i++) {
    Value *OldOperand = I->getOperand(0);
    Value *Src = F.getArg(5);
    IB.connectToSink(BB, {I}, Src);
    Value *NewOperand = I->getOperand(0);
    Modified |= (OldOperand != NewOperand);
    ASSERT_FALSE(verifyModule(*M, &errs()));
  }
  ASSERT_FALSE(Modified);
}

TEST(RandomIRBuilderTest, DoNotCallPointerWhenSink) {
  const char *Source = "\n\
        declare void @g()  \n\
        define void @f(ptr %ptr) {  \n\
        Entry:   \n\
            call void @g()  \n\
            ret void \n\
        }";
  LLVMContext Ctx;
  std::mt19937 mt(Seed);
  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);

  RandomIRBuilder IB(RandInt(mt), {});
  std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
  Function &F = *M->getFunction("f");
  BasicBlock &BB = F.getEntryBlock();
  bool Modified = false;

  Instruction *I = &*BB.begin();
  for (int i = 0; i < 20; i++) {
    Value *OldOperand = I->getOperand(0);
    Value *Src = F.getArg(0);
    IB.connectToSink(BB, {I}, Src);
    Value *NewOperand = I->getOperand(0);
    Modified |= (OldOperand != NewOperand);
    ASSERT_FALSE(verifyModule(*M, &errs()));
  }
  ASSERT_FALSE(Modified);
}

TEST(RandomIRBuilderTest, SrcAndSinkWOrphanBlock) {
  const char *Source = "\n\
        define i1 @test(i1 %Bool, i32 %Int, i64 %Long) {   \n\
        Entry:    \n\
            %Eq0 = icmp eq i64 %Long, 0 \n\
            br i1 %Eq0, label %True, label %False \n\
        True: \n\
            %Or = or i1 %Bool, %Eq0 \n\
            ret i1 %Or \n\
        False: \n\
            %And = and i1 %Bool, %Eq0 \n\
            ret i1 %And \n\
        Orphan_1:  \n\
            %NotBool = sub i1 1, %Bool \n\
            ret i1 %NotBool \n\
        Orphan_2:  \n\
            %Le42 = icmp sle i32 %Int, 42 \n\
            ret i1 %Le42 \n\
        }";
  LLVMContext Ctx;
  std::mt19937 mt(Seed);
  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
  std::array<Type *, 3> IntTys(
      {Type::getInt64Ty(Ctx), Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)});
  std::vector<Value *> Constants;
  for (Type *IntTy : IntTys) {
    for (size_t v : {1, 42}) {
      Constants.push_back(ConstantInt::get(IntTy, v));
    }
  }
  for (int i = 0; i < 10; i++) {
    RandomIRBuilder IB(RandInt(mt), IntTys);
    std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
    Function &F = *M->getFunction("test");
    for (BasicBlock &BB : F) {
      SmallVector<Instruction *, 4> Insts;
      for (Instruction &I : BB) {
        Insts.push_back(&I);
      }
      for (int j = 0; j < 10; j++) {
        IB.findOrCreateSource(BB, Insts);
      }
      for (Value *V : Constants) {
        IB.connectToSink(BB, Insts, V);
      }
    }
  }
}
} // namespace