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