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