llvm/lib/FuzzMutate/IRMutator.cpp

   1 //===-- IRMutator.cpp -----------------------------------------------------===//
   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/IRMutator.h"
  10 #include "llvm/ADT/STLExtras.h"
  11 #include "llvm/ADT/SmallSet.h"
  12 #include "llvm/Analysis/TargetLibraryInfo.h"
  13 #include "llvm/Bitcode/BitcodeReader.h"
  14 #include "llvm/Bitcode/BitcodeWriter.h"
  15 #include "llvm/FuzzMutate/Operations.h"
  16 #include "llvm/FuzzMutate/Random.h"
  17 #include "llvm/FuzzMutate/RandomIRBuilder.h"
  18 #include "llvm/IR/BasicBlock.h"
  19 #include "llvm/IR/FMF.h"
  20 #include "llvm/IR/Function.h"
  21 #include "llvm/IR/InstIterator.h"
  22 #include "llvm/IR/Instructions.h"
  23 #include "llvm/IR/Module.h"
  24 #include "llvm/IR/Operator.h"
  25 #include "llvm/IR/Verifier.h"
  26 #include "llvm/Support/MemoryBuffer.h"
  27 #include "llvm/Support/SourceMgr.h"
  28 #include "llvm/Transforms/Scalar/DCE.h"
  29 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  30 #include <map>
  31 #include <optional>
  32
  33 using namespace llvm;
  34
  35 void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
  36   auto RS = makeSampler<Function *>(IB.Rand);
  37   for (Function &F : M)
  38     if (!F.isDeclaration())
  39       RS.sample(&F, /*Weight=*/1);
  40
  41   while (RS.totalWeight() < IB.MinFunctionNum) {
  42     Function *F = IB.createFunctionDefinition(M);
  43     RS.sample(F, /*Weight=*/1);
  44   }
  45   mutate(*RS.getSelection(), IB);
  46 }
  47
  48 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
  49   auto Range = make_filter_range(make_pointer_range(F),
  50                                  [](BasicBlock *BB) { return !BB->isEHPad(); });
  51
  52   mutate(*makeSampler(IB.Rand, Range).getSelection(), IB);
  53 }
  54
  55 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
  56   mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
  57 }
  58
  59 size_t llvm::IRMutator::getModuleSize(const Module &M) {
  60   return M.getInstructionCount() + M.size() + M.global_size() + M.alias_size();
  61 }
  62
  63 void IRMutator::mutateModule(Module &M, int Seed, size_t MaxSize) {
  64   std::vector<Type *> Types;
  65   for (const auto &Getter : AllowedTypes)
  66     Types.push_back(Getter(M.getContext()));
  67   RandomIRBuilder IB(Seed, Types);
  68
  69   size_t CurSize = IRMutator::getModuleSize(M);
  70   auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
  71   for (const auto &Strategy : Strategies)
  72     RS.sample(Strategy.get(),
  73               Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
  74   if (RS.totalWeight() == 0)
  75     return;
  76   auto Strategy = RS.getSelection();
  77
  78   Strategy->mutate(M, IB);
  79 }
  80
  81 static void eliminateDeadCode(Function &F) {
  82   FunctionPassManager FPM;
  83   FPM.addPass(DCEPass());
  84   FunctionAnalysisManager FAM;
  85   FAM.registerPass([&] { return TargetLibraryAnalysis(); });
  86   FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
  87   FPM.run(F, FAM);
  88 }
  89
  90 void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
  91   IRMutationStrategy::mutate(F, IB);
  92   eliminateDeadCode(F);
  93 }
  94
  95 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
  96   std::vector<fuzzerop::OpDescriptor> Ops;
  97   describeFuzzerIntOps(Ops);
  98   describeFuzzerFloatOps(Ops);
  99   describeFuzzerControlFlowOps(Ops);
 100   describeFuzzerPointerOps(Ops);
 101   describeFuzzerAggregateOps(Ops);
 102   describeFuzzerVectorOps(Ops);
 103   return Ops;
 104 }
 105
 106 std::optional<fuzzerop::OpDescriptor>
 107 InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
 108   auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
 109     return Op.SourcePreds[0].matches({}, Src);
 110   };
 111   auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
 112   if (RS.isEmpty())
 113     return std::nullopt;
 114   return *RS;
 115 }
 116
 117 void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 118   SmallVector<Instruction *, 32> Insts;
 119   for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
 120     Insts.push_back(&*I);
 121   if (Insts.size() < 1)
 122     return;
 123
 124   // Choose an insertion point for our new instruction.
 125   size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
 126
 127   auto InstsBefore = ArrayRef(Insts).slice(0, IP);
 128   auto InstsAfter = ArrayRef(Insts).slice(IP);
 129
 130   // Choose a source, which will be used to constrain the operation selection.
 131   SmallVector<Value *, 2> Srcs;
 132   Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore));
 133
 134   // Choose an operation that's constrained to be valid for the type of the
 135   // source, collect any other sources it needs, and then build it.
 136   auto OpDesc = chooseOperation(Srcs[0], IB);
 137   // Bail if no operation was found
 138   if (!OpDesc)
 139     return;
 140
 141   for (const auto &Pred : ArrayRef(OpDesc->SourcePreds).slice(1))
 142     Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
 143
 144   if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) {
 145     // Find a sink and wire up the results of the operation.
 146     IB.connectToSink(BB, InstsAfter, Op);
 147   }
 148 }
 149
 150 uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize,
 151                                           uint64_t CurrentWeight) {
 152   // If we have less than 200 bytes, panic and try to always delete.
 153   if (CurrentSize > MaxSize - 200)
 154     return CurrentWeight ? CurrentWeight * 100 : 1;
 155   // Draw a line starting from when we only have 1k left and increasing linearly
 156   // to double the current weight.
 157   int64_t Line = (-2 * static_cast<int64_t>(CurrentWeight)) *
 158                  (static_cast<int64_t>(MaxSize) -
 159                   static_cast<int64_t>(CurrentSize) - 1000) /
 160                  1000;
 161   // Clamp negative weights to zero.
 162   if (Line < 0)
 163     return 0;
 164   return Line;
 165 }
 166
 167 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
 168   auto RS = makeSampler<Instruction *>(IB.Rand);
 169   for (Instruction &Inst : instructions(F)) {
 170     // TODO: We can't handle these instructions.
 171     if (Inst.isTerminator() || Inst.isEHPad() || Inst.isSwiftError() ||
 172         isa<PHINode>(Inst))
 173       continue;
 174
 175     RS.sample(&Inst, /*Weight=*/1);
 176   }
 177   if (RS.isEmpty())
 178     return;
 179
 180   // Delete the instruction.
 181   mutate(*RS.getSelection(), IB);
 182   // Clean up any dead code that's left over after removing the instruction.
 183   eliminateDeadCode(F);
 184 }
 185
 186 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
 187   assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
 188
 189   if (Inst.getType()->isVoidTy()) {
 190     // Instructions with void type (ie, store) have no uses to worry about. Just
 191     // erase it and move on.
 192     Inst.eraseFromParent();
 193     return;
 194   }
 195
 196   // Otherwise we need to find some other value with the right type to keep the
 197   // users happy.
 198   auto Pred = fuzzerop::onlyType(Inst.getType());
 199   auto RS = makeSampler<Value *>(IB.Rand);
 200   SmallVector<Instruction *, 32> InstsBefore;
 201   BasicBlock *BB = Inst.getParent();
 202   for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
 203        ++I) {
 204     if (Pred.matches({}, &*I))
 205       RS.sample(&*I, /*Weight=*/1);
 206     InstsBefore.push_back(&*I);
 207   }
 208   if (!RS)
 209     RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
 210
 211   Inst.replaceAllUsesWith(RS.getSelection());
 212   Inst.eraseFromParent();
 213 }
 214
 215 void InstModificationIRStrategy::mutate(Instruction &Inst,
 216                                         RandomIRBuilder &IB) {
 217   SmallVector<std::function<void()>, 8> Modifications;
 218   CmpInst *CI = nullptr;
 219   GetElementPtrInst *GEP = nullptr;
 220   switch (Inst.getOpcode()) {
 221   default:
 222     break;
 223   // Add nsw, nuw flag
 224   case Instruction::Add:
 225   case Instruction::Mul:
 226   case Instruction::Sub:
 227   case Instruction::Shl:
 228     Modifications.push_back(
 229         [&Inst]() { Inst.setHasNoSignedWrap(!Inst.hasNoSignedWrap()); });
 230     Modifications.push_back(
 231         [&Inst]() { Inst.setHasNoUnsignedWrap(!Inst.hasNoUnsignedWrap()); });
 232     break;
 233   case Instruction::ICmp:
 234     CI = cast<ICmpInst>(&Inst);
 235     for (unsigned p = CmpInst::FIRST_ICMP_PREDICATE;
 236          p <= CmpInst::LAST_ICMP_PREDICATE; p++) {
 237       Modifications.push_back(
 238           [CI, p]() { CI->setPredicate(static_cast<CmpInst::Predicate>(p)); });
 239     }
 240     break;
 241   // Add inbound flag.
 242   case Instruction::GetElementPtr:
 243     GEP = cast<GetElementPtrInst>(&Inst);
 244     Modifications.push_back(
 245         [GEP]() { GEP->setIsInBounds(!GEP->isInBounds()); });
 246     break;
 247   // Add exact flag.
 248   case Instruction::UDiv:
 249   case Instruction::SDiv:
 250   case Instruction::LShr:
 251   case Instruction::AShr:
 252     Modifications.push_back([&Inst] { Inst.setIsExact(!Inst.isExact()); });
 253     break;
 254
 255   case Instruction::FCmp:
 256     CI = cast<FCmpInst>(&Inst);
 257     for (unsigned p = CmpInst::FIRST_FCMP_PREDICATE;
 258          p <= CmpInst::LAST_FCMP_PREDICATE; p++) {
 259       Modifications.push_back(
 260           [CI, p]() { CI->setPredicate(static_cast<CmpInst::Predicate>(p)); });
 261     }
 262     break;
 263   }
 264
 265   // Add fast math flag if possible.
 266   if (isa<FPMathOperator>(&Inst)) {
 267     // Try setting everything unless they are already on.
 268     Modifications.push_back(
 269         [&Inst] { Inst.setFast(!Inst.getFastMathFlags().all()); });
 270     // Try unsetting everything unless they are already off.
 271     Modifications.push_back(
 272         [&Inst] { Inst.setFast(!Inst.getFastMathFlags().none()); });
 273     // Individual setting by flipping the bit
 274     Modifications.push_back(
 275         [&Inst] { Inst.setHasAllowReassoc(!Inst.hasAllowReassoc()); });
 276     Modifications.push_back([&Inst] { Inst.setHasNoNaNs(!Inst.hasNoNaNs()); });
 277     Modifications.push_back([&Inst] { Inst.setHasNoInfs(!Inst.hasNoInfs()); });
 278     Modifications.push_back(
 279         [&Inst] { Inst.setHasNoSignedZeros(!Inst.hasNoSignedZeros()); });
 280     Modifications.push_back(
 281         [&Inst] { Inst.setHasAllowReciprocal(!Inst.hasAllowReciprocal()); });
 282     Modifications.push_back(
 283         [&Inst] { Inst.setHasAllowContract(!Inst.hasAllowContract()); });
 284     Modifications.push_back(
 285         [&Inst] { Inst.setHasApproxFunc(!Inst.hasApproxFunc()); });
 286   }
 287
 288   // Randomly switch operands of instructions
 289   std::pair<int, int> NoneItem({-1, -1}), ShuffleItems(NoneItem);
 290   switch (Inst.getOpcode()) {
 291   case Instruction::SDiv:
 292   case Instruction::UDiv:
 293   case Instruction::SRem:
 294   case Instruction::URem:
 295   case Instruction::FDiv:
 296   case Instruction::FRem: {
 297     // Verify that the after shuffle the second operand is not
 298     // constant 0.
 299     Value *Operand = Inst.getOperand(0);
 300     if (Constant *C = dyn_cast<Constant>(Operand)) {
 301       if (!C->isZeroValue()) {
 302         ShuffleItems = {0, 1};
 303       }
 304     }
 305     break;
 306   }
 307   case Instruction::Select:
 308     ShuffleItems = {1, 2};
 309     break;
 310   case Instruction::Add:
 311   case Instruction::Sub:
 312   case Instruction::Mul:
 313   case Instruction::Shl:
 314   case Instruction::LShr:
 315   case Instruction::AShr:
 316   case Instruction::And:
 317   case Instruction::Or:
 318   case Instruction::Xor:
 319   case Instruction::FAdd:
 320   case Instruction::FSub:
 321   case Instruction::FMul:
 322   case Instruction::ICmp:
 323   case Instruction::FCmp:
 324   case Instruction::ShuffleVector:
 325     ShuffleItems = {0, 1};
 326     break;
 327   }
 328   if (ShuffleItems != NoneItem) {
 329     Modifications.push_back([&Inst, &ShuffleItems]() {
 330       Value *Op0 = Inst.getOperand(ShuffleItems.first);
 331       Inst.setOperand(ShuffleItems.first, Inst.getOperand(ShuffleItems.second));
 332       Inst.setOperand(ShuffleItems.second, Op0);
 333     });
 334   }
 335
 336   auto RS = makeSampler(IB.Rand, Modifications);
 337   if (RS)
 338     RS.getSelection()();
 339 }
 340
 341 /// Return a case value that is not already taken to make sure we don't have two
 342 /// cases with same value.
 343 static uint64_t getUniqueCaseValue(SmallSet<uint64_t, 4> &CasesTaken,
 344                                    uint64_t MaxValue, RandomIRBuilder &IB) {
 345   uint64_t tmp;
 346   do {
 347     tmp = uniform<uint64_t>(IB.Rand, 0, MaxValue);
 348   } while (CasesTaken.count(tmp) != 0);
 349   CasesTaken.insert(tmp);
 350   return tmp;
 351 }
 352
 353 void InsertFunctionStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 354   Module *M = BB.getParent()->getParent();
 355   // If nullptr is selected, we will create a new function declaration.
 356   SmallVector<Function *, 32> Functions({nullptr});
 357   for (Function &F : M->functions()) {
 358     Functions.push_back(&F);
 359   }
 360
 361   auto RS = makeSampler(IB.Rand, Functions);
 362   Function *F = RS.getSelection();
 363   if (!F) {
 364     F = IB.createFunctionDeclaration(*M);
 365   }
 366
 367   FunctionType *FTy = F->getFunctionType();
 368   SmallVector<fuzzerop::SourcePred, 2> SourcePreds;
 369   if (!F->arg_empty()) {
 370     for (Type *ArgTy : FTy->params()) {
 371       SourcePreds.push_back(fuzzerop::onlyType(ArgTy));
 372     }
 373   }
 374   bool isRetVoid = (F->getReturnType() == Type::getVoidTy(M->getContext()));
 375   auto BuilderFunc = [FTy, F, isRetVoid](ArrayRef<Value *> Srcs,
 376                                          Instruction *Inst) {
 377     StringRef Name = isRetVoid ? nullptr : "C";
 378     CallInst *Call = CallInst::Create(FTy, F, Srcs, Name, Inst);
 379     // Don't return this call inst if it return void as it can't be sinked.
 380     return isRetVoid ? nullptr : Call;
 381   };
 382
 383   SmallVector<Instruction *, 32> Insts;
 384   for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
 385     Insts.push_back(&I);
 386   if (Insts.size() < 1)
 387     return;
 388
 389   // Choose an insertion point for our new call instruction.
 390   uint64_t IP = uniform<uint64_t>(IB.Rand, 0, Insts.size() - 1);
 391
 392   auto InstsBefore = ArrayRef(Insts).slice(0, IP);
 393   auto InstsAfter = ArrayRef(Insts).slice(IP);
 394
 395   // Choose a source, which will be used to constrain the operation selection.
 396   SmallVector<Value *, 2> Srcs;
 397
 398   for (const auto &Pred : ArrayRef(SourcePreds)) {
 399     Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
 400   }
 401
 402   if (Value *Op = BuilderFunc(Srcs, Insts[IP])) {
 403     // Find a sink and wire up the results of the operation.
 404     IB.connectToSink(BB, InstsAfter, Op);
 405   }
 406 }
 407
 408 void InsertCFGStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 409   SmallVector<Instruction *, 32> Insts;
 410   for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
 411     Insts.push_back(&I);
 412   if (Insts.size() < 1)
 413     return;
 414
 415   // Choose a point where we split the block.
 416   uint64_t IP = uniform<uint64_t>(IB.Rand, 0, Insts.size() - 1);
 417   auto InstsBeforeSplit = ArrayRef(Insts).slice(0, IP);
 418
 419   // `Sink` inherits Blocks' terminator, `Source` will have a BranchInst
 420   // directly jumps to `Sink`. Here, we have to create a new terminator for
 421   // `Source`.
 422   BasicBlock *Block = Insts[IP]->getParent();
 423   BasicBlock *Source = Block;
 424   BasicBlock *Sink = Block->splitBasicBlock(Insts[IP], "BB");
 425
 426   Function *F = BB.getParent();
 427   LLVMContext &C = F->getParent()->getContext();
 428   // A coin decides if it is branch or switch
 429   if (uniform<uint64_t>(IB.Rand, 0, 1)) {
 430     // Branch
 431     BasicBlock *IfTrue = BasicBlock::Create(C, "T", F);
 432     BasicBlock *IfFalse = BasicBlock::Create(C, "F", F);
 433     Value *Cond =
 434         IB.findOrCreateSource(*Source, InstsBeforeSplit, {},
 435                               fuzzerop::onlyType(Type::getInt1Ty(C)), false);
 436     BranchInst *Branch = BranchInst::Create(IfTrue, IfFalse, Cond);
 437     // Remove the old terminator.
 438     ReplaceInstWithInst(Source->getTerminator(), Branch);
 439     // Connect these blocks to `Sink`
 440     connectBlocksToSink({IfTrue, IfFalse}, Sink, IB);
 441   } else {
 442     // Switch
 443     // Determine Integer type, it IS possible we use a boolean to switch.
 444     auto RS =
 445         makeSampler(IB.Rand, make_filter_range(IB.KnownTypes, [](Type *Ty) {
 446                       return Ty->isIntegerTy();
 447                     }));
 448     assert(RS && "There is no integer type in all allowed types, is the "
 449                  "setting correct?");
 450     Type *Ty = RS.getSelection();
 451     IntegerType *IntTy = cast<IntegerType>(Ty);
 452
 453     uint64_t BitSize = IntTy->getBitWidth();
 454     uint64_t MaxCaseVal =
 455         (BitSize >= 64) ? (uint64_t)-1 : ((uint64_t)1 << BitSize) - 1;
 456     // Create Switch inst in Block
 457     Value *Cond = IB.findOrCreateSource(*Source, InstsBeforeSplit, {},
 458                                         fuzzerop::onlyType(IntTy), false);
 459     BasicBlock *DefaultBlock = BasicBlock::Create(C, "SW_D", F);
 460     uint64_t NumCases = uniform<uint64_t>(IB.Rand, 1, MaxNumCases);
 461     NumCases = (NumCases > MaxCaseVal) ? MaxCaseVal + 1 : NumCases;
 462     SwitchInst *Switch = SwitchInst::Create(Cond, DefaultBlock, NumCases);
 463     // Remove the old terminator.
 464     ReplaceInstWithInst(Source->getTerminator(), Switch);
 465
 466     // Create blocks, for each block assign a case value.
 467     SmallVector<BasicBlock *, 4> Blocks({DefaultBlock});
 468     SmallSet<uint64_t, 4> CasesTaken;
 469     for (uint64_t i = 0; i < NumCases; i++) {
 470       uint64_t CaseVal = getUniqueCaseValue(CasesTaken, MaxCaseVal, IB);
 471       BasicBlock *CaseBlock = BasicBlock::Create(C, "SW_C", F);
 472       ConstantInt *OnValue = ConstantInt::get(IntTy, CaseVal);
 473       Switch->addCase(OnValue, CaseBlock);
 474       Blocks.push_back(CaseBlock);
 475     }
 476
 477     // Connect these blocks to `Sink`
 478     connectBlocksToSink(Blocks, Sink, IB);
 479   }
 480 }
 481
 482 /// The caller has to guarantee that these blocks are "empty", i.e. it doesn't
 483 /// even have terminator.
 484 void InsertCFGStrategy::connectBlocksToSink(ArrayRef<BasicBlock *> Blocks,
 485                                             BasicBlock *Sink,
 486                                             RandomIRBuilder &IB) {
 487   uint64_t DirectSinkIdx = uniform<uint64_t>(IB.Rand, 0, Blocks.size() - 1);
 488   for (uint64_t i = 0; i < Blocks.size(); i++) {
 489     // We have at least one block that directly goes to sink.
 490     CFGToSink ToSink = (i == DirectSinkIdx)
 491                            ? CFGToSink::DirectSink
 492                            : static_cast<CFGToSink>(uniform<uint64_t>(
 493                                  IB.Rand, 0, CFGToSink::EndOfCFGToLink - 1));
 494     BasicBlock *BB = Blocks[i];
 495     Function *F = BB->getParent();
 496     LLVMContext &C = F->getParent()->getContext();
 497     switch (ToSink) {
 498     case CFGToSink::Return: {
 499       Type *RetTy = F->getReturnType();
 500       Value *RetValue = nullptr;
 501       if (!RetTy->isVoidTy())
 502         RetValue =
 503             IB.findOrCreateSource(*BB, {}, {}, fuzzerop::onlyType(RetTy));
 504       ReturnInst::Create(C, RetValue, BB);
 505       break;
 506     }
 507     case CFGToSink::DirectSink: {
 508       BranchInst::Create(Sink, BB);
 509       break;
 510     }
 511     case CFGToSink::SinkOrSelfLoop: {
 512       SmallVector<BasicBlock *, 2> Branches({Sink, BB});
 513       // A coin decides which block is true branch.
 514       uint64_t coin = uniform<uint64_t>(IB.Rand, 0, 1);
 515       Value *Cond = IB.findOrCreateSource(
 516           *BB, {}, {}, fuzzerop::onlyType(Type::getInt1Ty(C)), false);
 517       BranchInst::Create(Branches[coin], Branches[1 - coin], Cond, BB);
 518       break;
 519     }
 520     case CFGToSink::EndOfCFGToLink:
 521       llvm_unreachable("EndOfCFGToLink executed, something's wrong.");
 522     }
 523   }
 524 }
 525
 526 void InsertPHIStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 527   // Can't insert PHI node to entry node.
 528   if (&BB == &BB.getParent()->getEntryBlock())
 529     return;
 530   Type *Ty = IB.randomType();
 531   PHINode *PHI = PHINode::Create(Ty, llvm::pred_size(&BB), "", &BB.front());
 532
 533   // Use a map to make sure the same incoming basic block has the same value.
 534   DenseMap<BasicBlock *, Value *> IncomingValues;
 535   for (BasicBlock *Pred : predecessors(&BB)) {
 536     Value *Src = IncomingValues[Pred];
 537     // If `Pred` is not in the map yet, we'll get a nullptr.
 538     if (!Src) {
 539       SmallVector<Instruction *, 32> Insts;
 540       for (auto I = Pred->begin(); I != Pred->end(); ++I)
 541         Insts.push_back(&*I);
 542       // There is no need to inform IB what previously used values are if we are
 543       // using `onlyType`
 544       Src = IB.findOrCreateSource(*Pred, Insts, {}, fuzzerop::onlyType(Ty));
 545       IncomingValues[Pred] = Src;
 546     }
 547     PHI->addIncoming(Src, Pred);
 548   }
 549   SmallVector<Instruction *, 32> InstsAfter;
 550   for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
 551     InstsAfter.push_back(&I);
 552   IB.connectToSink(BB, InstsAfter, PHI);
 553 }
 554
 555 void SinkInstructionStrategy::mutate(Function &F, RandomIRBuilder &IB) {
 556   for (BasicBlock &BB : F) {
 557     this->mutate(BB, IB);
 558   }
 559 }
 560 void SinkInstructionStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 561   SmallVector<Instruction *, 32> Insts;
 562   for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
 563     Insts.push_back(&I);
 564   if (Insts.size() < 1)
 565     return;
 566   // Choose an Instruction to mutate.
 567   uint64_t Idx = uniform<uint64_t>(IB.Rand, 0, Insts.size() - 1);
 568   Instruction *Inst = Insts[Idx];
 569   // `Idx + 1` so we don't sink to ourselves.
 570   auto InstsAfter = ArrayRef(Insts).slice(Idx + 1);
 571   LLVMContext &C = BB.getParent()->getParent()->getContext();
 572   // Don't sink terminators, void function calls, etc.
 573   if (Inst->getType() != Type::getVoidTy(C))
 574     // Find a new sink and wire up the results of the operation.
 575     IB.connectToSink(BB, InstsAfter, Inst);
 576 }
 577
 578 void ShuffleBlockStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 579   // A deterministic alternative to SmallPtrSet with the same lookup
 580   // performance.
 581   std::map<size_t, Instruction *> AliveInsts;
 582   std::map<Instruction *, size_t> AliveInstsLookup;
 583   size_t InsertIdx = 0;
 584   for (auto &I : make_early_inc_range(make_range(
 585            BB.getFirstInsertionPt(), BB.getTerminator()->getIterator()))) {
 586     // First gather all instructions that can be shuffled. Don't take
 587     // terminator.
 588     AliveInsts.insert({InsertIdx, &I});
 589     AliveInstsLookup.insert({&I, InsertIdx++});
 590     // Then remove these instructions from the block
 591     I.removeFromParent();
 592   }
 593
 594   // Shuffle these instructions using topological sort.
 595   // Returns false if all current instruction's dependencies in this block have
 596   // been shuffled. If so, this instruction can be shuffled too.
 597   auto hasAliveParent = [&AliveInsts, &AliveInstsLookup](size_t Index) {
 598     for (Value *O : AliveInsts[Index]->operands()) {
 599       Instruction *P = dyn_cast<Instruction>(O);
 600       if (P && AliveInstsLookup.count(P))
 601         return true;
 602     }
 603     return false;
 604   };
 605   // Get all alive instructions that depend on the current instruction.
 606   // Takes Instruction* instead of index because the instruction is already
 607   // shuffled.
 608   auto getAliveChildren = [&AliveInstsLookup](Instruction *I) {
 609     SmallSetVector<size_t, 8> Children;
 610     for (Value *U : I->users()) {
 611       Instruction *P = dyn_cast<Instruction>(U);
 612       if (P && AliveInstsLookup.count(P))
 613         Children.insert(AliveInstsLookup[P]);
 614     }
 615     return Children;
 616   };
 617   SmallSet<size_t, 8> RootIndices;
 618   SmallVector<Instruction *, 8> Insts;
 619   for (const auto &[Index, Inst] : AliveInsts) {
 620     if (!hasAliveParent(Index))
 621       RootIndices.insert(Index);
 622   }
 623   // Topological sort by randomly selecting a node without a parent, or root.
 624   while (!RootIndices.empty()) {
 625     auto RS = makeSampler<size_t>(IB.Rand);
 626     for (size_t RootIdx : RootIndices)
 627       RS.sample(RootIdx, 1);
 628     size_t RootIdx = RS.getSelection();
 629
 630     RootIndices.erase(RootIdx);
 631     Instruction *Root = AliveInsts[RootIdx];
 632     AliveInsts.erase(RootIdx);
 633     AliveInstsLookup.erase(Root);
 634     Insts.push_back(Root);
 635
 636     for (size_t Child : getAliveChildren(Root)) {
 637       if (!hasAliveParent(Child)) {
 638         RootIndices.insert(Child);
 639       }
 640     }
 641   }
 642
 643   Instruction *Terminator = BB.getTerminator();
 644   // Then put instructions back.
 645   for (Instruction *I : Insts) {
 646     I->insertBefore(Terminator);
 647   }
 648 }
 649
 650 std::unique_ptr<Module> llvm::parseModule(const uint8_t *Data, size_t Size,
 651                                           LLVMContext &Context) {
 652
 653   if (Size <= 1)
 654     // We get bogus data given an empty corpus - just create a new module.
 655     return std::make_unique<Module>("M", Context);
 656
 657   auto Buffer = MemoryBuffer::getMemBuffer(
 658       StringRef(reinterpret_cast<const char *>(Data), Size), "Fuzzer input",
 659       /*RequiresNullTerminator=*/false);
 660
 661   SMDiagnostic Err;
 662   auto M = parseBitcodeFile(Buffer->getMemBufferRef(), Context);
 663   if (Error E = M.takeError()) {
 664     errs() << toString(std::move(E)) << "\n";
 665     return nullptr;
 666   }
 667   return std::move(M.get());
 668 }
 669
 670 size_t llvm::writeModule(const Module &M, uint8_t *Dest, size_t MaxSize) {
 671   std::string Buf;
 672   {
 673     raw_string_ostream OS(Buf);
 674     WriteBitcodeToFile(M, OS);
 675   }
 676   if (Buf.size() > MaxSize)
 677     return 0;
 678   memcpy(Dest, Buf.data(), Buf.size());
 679   return Buf.size();
 680 }
 681
 682 std::unique_ptr<Module> llvm::parseAndVerify(const uint8_t *Data, size_t Size,
 683                                              LLVMContext &Context) {
 684   auto M = parseModule(Data, Size, Context);
 685   if (!M || verifyModule(*M, &errs()))
 686     return nullptr;
 687
 688   return M;
 689 }