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