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 
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 
35 void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
36   auto RS = makeSampler<Function *>(IB.Rand);
37   for (Function &F : M)
38     if (!F.isDeclaration())
39       RS.sample(&F, /*Weight=*/1);
40 
41   if (RS.isEmpty())
42     createEmptyFunction(M);
43   else
44     mutate(*RS.getSelection(), IB);
45 }
46 
47 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
48   mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
49 }
50 
51 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
52   mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
53 }
54 
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 
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 
80 void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
81   IRMutationStrategy::mutate(F, IB);
82   eliminateDeadCode(F);
83 }
84 
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>
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 
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 
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   int64_t Line = (-2 * static_cast<int64_t>(CurrentWeight)) *
148                  (static_cast<int64_t>(MaxSize) -
149                   static_cast<int64_t>(CurrentSize) - 1000) /
150                  1000;
151   // Clamp negative weights to zero.
152   if (Line < 0)
153     return 0;
154   return Line;
155 }
156 
157 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
158   auto RS = makeSampler<Instruction *>(IB.Rand);
159   for (Instruction &Inst : instructions(F)) {
160     // TODO: We can't handle these instructions.
161     if (Inst.isTerminator() || Inst.isEHPad() ||
162         Inst.isSwiftError() || isa<PHINode>(Inst))
163       continue;
164 
165     RS.sample(&Inst, /*Weight=*/1);
166   }
167   if (RS.isEmpty())
168     return;
169 
170   // Delete the instruction.
171   mutate(*RS.getSelection(), IB);
172   // Clean up any dead code that's left over after removing the instruction.
173   eliminateDeadCode(F);
174 }
175 
176 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
177   assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
178 
179   if (Inst.getType()->isVoidTy()) {
180     // Instructions with void type (ie, store) have no uses to worry about. Just
181     // erase it and move on.
182     Inst.eraseFromParent();
183     return;
184   }
185 
186   // Otherwise we need to find some other value with the right type to keep the
187   // users happy.
188   auto Pred = fuzzerop::onlyType(Inst.getType());
189   auto RS = makeSampler<Value *>(IB.Rand);
190   SmallVector<Instruction *, 32> InstsBefore;
191   BasicBlock *BB = Inst.getParent();
192   for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
193        ++I) {
194     if (Pred.matches({}, &*I))
195       RS.sample(&*I, /*Weight=*/1);
196     InstsBefore.push_back(&*I);
197   }
198   if (!RS)
199     RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
200 
201   Inst.replaceAllUsesWith(RS.getSelection());
202   Inst.eraseFromParent();
203 }
204 
205 void InstModificationIRStrategy::mutate(Instruction &Inst,
206                                         RandomIRBuilder &IB) {
207   SmallVector<std::function<void()>, 8> Modifications;
208   CmpInst *CI = nullptr;
209   GetElementPtrInst *GEP = nullptr;
210   switch (Inst.getOpcode()) {
211   default:
212     break;
213   case Instruction::Add:
214   case Instruction::Mul:
215   case Instruction::Sub:
216   case Instruction::Shl:
217     Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(true); }),
218         Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(false); });
219     Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(true); });
220     Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(false); });
221 
222     break;
223   case Instruction::ICmp:
224     CI = cast<ICmpInst>(&Inst);
225     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_EQ); });
226     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_NE); });
227     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGT); });
228     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGE); });
229     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULT); });
230     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULE); });
231     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGT); });
232     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGE); });
233     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLT); });
234     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLE); });
235     break;
236   case Instruction::GetElementPtr:
237     GEP = cast<GetElementPtrInst>(&Inst);
238     Modifications.push_back([GEP]() { GEP->setIsInBounds(true); });
239     Modifications.push_back([GEP]() { GEP->setIsInBounds(false); });
240     break;
241   }
242 
243   auto RS = makeSampler(IB.Rand, Modifications);
244   if (RS)
245     RS.getSelection()();
246 }
247