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
35using namespace llvm;
36
37void 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
50void 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
57void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
58 mutate(I&: *makeSampler(RandGen&: IB.Rand, Items: make_pointer_range(Range&: BB)).getSelection(), IB);
59}
60
61size_t llvm::IRMutator::getModuleSize(const Module &M) {
62 return M.getInstructionCount() + M.size() + M.global_size() + M.alias_size();
63}
64
65void 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
83static 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
92void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
93 IRMutationStrategy::mutate(F, IB);
94 eliminateDeadCode(F);
95}
96
97std::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
108std::optional<fuzzerop::OpDescriptor>
109InjectorIRStrategy::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
119static 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
135static 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
151static inline iterator_range<BasicBlock::iterator>
152getInsertionRange(BasicBlock &BB) {
153 auto End = getEndIterator(BB);
154 return make_range(x: BB.getFirstInsertionPt(), y: End);
155}
156
157void 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
189uint64_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
206void 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
225void 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
254void 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.
382static 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.
398static 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
454void 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
510void 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.
585void 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
627void 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
655void SinkInstructionStrategy::mutate(Function &F, RandomIRBuilder &IB) {
656 for (BasicBlock &BB : F) {
657 this->mutate(BB, IB);
658 }
659}
660void 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
677void 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
752std::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
771size_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
783std::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