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