Line data Source code
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 :
26 1 : static void createEmptyFunction(Module &M) {
27 : // TODO: Some arguments and a return value would probably be more interesting.
28 1 : LLVMContext &Context = M.getContext();
29 2 : Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {},
30 1 : /*isVarArg=*/false),
31 : GlobalValue::ExternalLinkage, "f", &M);
32 1 : BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
33 1 : ReturnInst::Create(Context, BB);
34 1 : }
35 :
36 21 : void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
37 21 : if (M.empty())
38 1 : createEmptyFunction(M);
39 :
40 42 : auto RS = makeSampler<Function *>(IB.Rand);
41 52 : for (Function &F : M)
42 31 : if (!F.isDeclaration())
43 31 : RS.sample(&F, /*Weight=*/1);
44 21 : mutate(*RS.getSelection(), IB);
45 21 : }
46 :
47 1 : void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
48 2 : mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
49 1 : }
50 :
51 0 : void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
52 0 : mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
53 0 : }
54 :
55 21 : void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
56 : size_t MaxSize) {
57 : std::vector<Type *> Types;
58 168 : for (const auto &Getter : AllowedTypes)
59 294 : Types.push_back(Getter(M.getContext()));
60 21 : RandomIRBuilder IB(Seed, Types);
61 :
62 : auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
63 42 : for (const auto &Strategy : Strategies)
64 21 : RS.sample(Strategy.get(),
65 21 : Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
66 21 : auto Strategy = RS.getSelection();
67 :
68 21 : Strategy->mutate(M, IB);
69 21 : }
70 :
71 1 : static void eliminateDeadCode(Function &F) {
72 : FunctionPassManager FPM;
73 1 : FPM.addPass(DCEPass());
74 1 : FunctionAnalysisManager FAM;
75 1 : FAM.registerPass([&] { return TargetLibraryAnalysis(); });
76 1 : FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
77 1 : FPM.run(F, FAM);
78 1 : }
79 :
80 1 : void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
81 1 : IRMutationStrategy::mutate(F, IB);
82 1 : eliminateDeadCode(F);
83 1 : }
84 :
85 8 : std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
86 : std::vector<fuzzerop::OpDescriptor> Ops;
87 8 : describeFuzzerIntOps(Ops);
88 8 : describeFuzzerFloatOps(Ops);
89 8 : describeFuzzerControlFlowOps(Ops);
90 8 : describeFuzzerPointerOps(Ops);
91 8 : describeFuzzerAggregateOps(Ops);
92 8 : describeFuzzerVectorOps(Ops);
93 8 : return Ops;
94 : }
95 :
96 : Optional<fuzzerop::OpDescriptor>
97 1 : InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
98 : auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
99 51 : return Op.SourcePreds[0].matches({}, Src);
100 1 : };
101 1 : auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
102 1 : if (RS.isEmpty())
103 : return None;
104 : return *RS;
105 : }
106 :
107 1 : void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
108 : SmallVector<Instruction *, 32> Insts;
109 2 : for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
110 1 : Insts.push_back(&*I);
111 2 : if (Insts.size() < 1)
112 : return;
113 :
114 : // Choose an insertion point for our new instruction.
115 1 : size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
116 :
117 1 : auto InstsBefore = makeArrayRef(Insts).slice(0, IP);
118 1 : 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 1 : 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 1 : auto OpDesc = chooseOperation(Srcs[0], IB);
127 : // Bail if no operation was found
128 1 : if (!OpDesc)
129 : return;
130 :
131 2 : for (const auto &Pred : makeArrayRef(OpDesc->SourcePreds).slice(1))
132 1 : Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
133 :
134 2 : if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) {
135 : // Find a sink and wire up the results of the operation.
136 1 : IB.connectToSink(BB, InstsAfter, Op);
137 : }
138 : }
139 :
140 20 : 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 20 : if (CurrentSize > MaxSize - 200)
144 20 : 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 0 : int Line = (-2 * CurrentWeight) * (MaxSize - CurrentSize + 1000);
148 : // Clamp negative weights to zero.
149 0 : if (Line < 0)
150 : return 0;
151 0 : return Line;
152 : }
153 :
154 20 : void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
155 20 : auto RS = makeSampler<Instruction *>(IB.Rand);
156 60 : for (Instruction &Inst : instructions(F)) {
157 : // TODO: We can't handle these instructions.
158 20 : if (Inst.isTerminator() || Inst.isEHPad() ||
159 100 : Inst.isSwiftError() || isa<PHINode>(Inst))
160 60 : continue;
161 :
162 0 : RS.sample(&Inst, /*Weight=*/1);
163 : }
164 20 : if (RS.isEmpty())
165 20 : return;
166 :
167 : // Delete the instruction.
168 0 : mutate(*RS.getSelection(), IB);
169 : // Clean up any dead code that's left over after removing the instruction.
170 0 : eliminateDeadCode(F);
171 : }
172 :
173 0 : void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
174 : assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
175 :
176 0 : 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 0 : Inst.eraseFromParent();
180 0 : return;
181 : }
182 :
183 : // Otherwise we need to find some other value with the right type to keep the
184 : // users happy.
185 0 : auto Pred = fuzzerop::onlyType(Inst.getType());
186 0 : auto RS = makeSampler<Value *>(IB.Rand);
187 : SmallVector<Instruction *, 32> InstsBefore;
188 0 : BasicBlock *BB = Inst.getParent();
189 0 : for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
190 : ++I) {
191 0 : if (Pred.matches({}, &*I))
192 0 : RS.sample(&*I, /*Weight=*/1);
193 0 : InstsBefore.push_back(&*I);
194 : }
195 0 : if (!RS)
196 0 : RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
197 :
198 0 : Inst.replaceAllUsesWith(RS.getSelection());
199 0 : Inst.eraseFromParent();
200 : }
|
