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