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/Optional.h"
11 #include "llvm/Analysis/TargetLibraryInfo.h"
12 #include "llvm/FuzzMutate/Operations.h"
13 #include "llvm/FuzzMutate/Random.h"
14 #include "llvm/FuzzMutate/RandomIRBuilder.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Function.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Transforms/Scalar/DCE.h"
22
23 using namespace llvm;
24
createEmptyFunction(Module & M)25 static void createEmptyFunction(Module &M) {
26 // TODO: Some arguments and a return value would probably be more interesting.
27 LLVMContext &Context = M.getContext();
28 Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {},
29 /*isVarArg=*/false),
30 GlobalValue::ExternalLinkage, "f", &M);
31 BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
32 ReturnInst::Create(Context, BB);
33 }
34
mutate(Module & M,RandomIRBuilder & IB)35 void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
36 if (M.empty())
37 createEmptyFunction(M);
38
39 auto RS = makeSampler<Function *>(IB.Rand);
40 for (Function &F : M)
41 if (!F.isDeclaration())
42 RS.sample(&F, /*Weight=*/1);
43 mutate(*RS.getSelection(), IB);
44 }
45
mutate(Function & F,RandomIRBuilder & IB)46 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
47 mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
48 }
49
mutate(BasicBlock & BB,RandomIRBuilder & IB)50 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
51 mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
52 }
53
mutateModule(Module & M,int Seed,size_t CurSize,size_t MaxSize)54 void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
55 size_t MaxSize) {
56 std::vector<Type *> Types;
57 for (const auto &Getter : AllowedTypes)
58 Types.push_back(Getter(M.getContext()));
59 RandomIRBuilder IB(Seed, Types);
60
61 auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
62 for (const auto &Strategy : Strategies)
63 RS.sample(Strategy.get(),
64 Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
65 auto Strategy = RS.getSelection();
66
67 Strategy->mutate(M, IB);
68 }
69
eliminateDeadCode(Function & F)70 static void eliminateDeadCode(Function &F) {
71 FunctionPassManager FPM;
72 FPM.addPass(DCEPass());
73 FunctionAnalysisManager FAM;
74 FAM.registerPass([&] { return TargetLibraryAnalysis(); });
75 FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
76 FPM.run(F, FAM);
77 }
78
mutate(Function & F,RandomIRBuilder & IB)79 void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
80 IRMutationStrategy::mutate(F, IB);
81 eliminateDeadCode(F);
82 }
83
getDefaultOps()84 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
85 std::vector<fuzzerop::OpDescriptor> Ops;
86 describeFuzzerIntOps(Ops);
87 describeFuzzerFloatOps(Ops);
88 describeFuzzerControlFlowOps(Ops);
89 describeFuzzerPointerOps(Ops);
90 describeFuzzerAggregateOps(Ops);
91 describeFuzzerVectorOps(Ops);
92 return Ops;
93 }
94
95 Optional<fuzzerop::OpDescriptor>
chooseOperation(Value * Src,RandomIRBuilder & IB)96 InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
97 auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
98 return Op.SourcePreds[0].matches({}, Src);
99 };
100 auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
101 if (RS.isEmpty())
102 return None;
103 return *RS;
104 }
105
mutate(BasicBlock & BB,RandomIRBuilder & IB)106 void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
107 SmallVector<Instruction *, 32> Insts;
108 for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
109 Insts.push_back(&*I);
110 if (Insts.size() < 1)
111 return;
112
113 // Choose an insertion point for our new instruction.
114 size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
115
116 auto InstsBefore = makeArrayRef(Insts).slice(0, IP);
117 auto InstsAfter = makeArrayRef(Insts).slice(IP);
118
119 // Choose a source, which will be used to constrain the operation selection.
120 SmallVector<Value *, 2> Srcs;
121 Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore));
122
123 // Choose an operation that's constrained to be valid for the type of the
124 // source, collect any other sources it needs, and then build it.
125 auto OpDesc = chooseOperation(Srcs[0], IB);
126 // Bail if no operation was found
127 if (!OpDesc)
128 return;
129
130 for (const auto &Pred : makeArrayRef(OpDesc->SourcePreds).slice(1))
131 Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
132
133 if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) {
134 // Find a sink and wire up the results of the operation.
135 IB.connectToSink(BB, InstsAfter, Op);
136 }
137 }
138
getWeight(size_t CurrentSize,size_t MaxSize,uint64_t CurrentWeight)139 uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize,
140 uint64_t CurrentWeight) {
141 // If we have less than 200 bytes, panic and try to always delete.
142 if (CurrentSize > MaxSize - 200)
143 return CurrentWeight ? CurrentWeight * 100 : 1;
144 // Draw a line starting from when we only have 1k left and increasing linearly
145 // to double the current weight.
146 int Line = (-2 * CurrentWeight) * (MaxSize - CurrentSize + 1000);
147 // Clamp negative weights to zero.
148 if (Line < 0)
149 return 0;
150 return Line;
151 }
152
mutate(Function & F,RandomIRBuilder & IB)153 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
154 auto RS = makeSampler<Instruction *>(IB.Rand);
155 for (Instruction &Inst : instructions(F)) {
156 // TODO: We can't handle these instructions.
157 if (Inst.isTerminator() || Inst.isEHPad() ||
158 Inst.isSwiftError() || isa<PHINode>(Inst))
159 continue;
160
161 RS.sample(&Inst, /*Weight=*/1);
162 }
163 if (RS.isEmpty())
164 return;
165
166 // Delete the instruction.
167 mutate(*RS.getSelection(), IB);
168 // Clean up any dead code that's left over after removing the instruction.
169 eliminateDeadCode(F);
170 }
171
mutate(Instruction & Inst,RandomIRBuilder & IB)172 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
173 assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
174
175 if (Inst.getType()->isVoidTy()) {
176 // Instructions with void type (ie, store) have no uses to worry about. Just
177 // erase it and move on.
178 Inst.eraseFromParent();
179 return;
180 }
181
182 // Otherwise we need to find some other value with the right type to keep the
183 // users happy.
184 auto Pred = fuzzerop::onlyType(Inst.getType());
185 auto RS = makeSampler<Value *>(IB.Rand);
186 SmallVector<Instruction *, 32> InstsBefore;
187 BasicBlock *BB = Inst.getParent();
188 for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
189 ++I) {
190 if (Pred.matches({}, &*I))
191 RS.sample(&*I, /*Weight=*/1);
192 InstsBefore.push_back(&*I);
193 }
194 if (!RS)
195 RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
196
197 Inst.replaceAllUsesWith(RS.getSelection());
198 Inst.eraseFromParent();
199 }
200