LLVM  8.0.0svn
IRMutator.cpp
Go to the documentation of this file.
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 
11 #include "llvm/ADT/Optional.h"
14 #include "llvm/FuzzMutate/Random.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"
23 
24 using namespace llvm;
25 
26 static void createEmptyFunction(Module &M) {
27  // TODO: Some arguments and a return value would probably be more interesting.
30  /*isVarArg=*/false),
32  BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
33  ReturnInst::Create(Context, BB);
34 }
35 
37  if (M.empty())
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 
48  mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
49 }
50 
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) {
73  FPM.addPass(DCEPass());
75  FAM.registerPass([&] { return TargetLibraryAnalysis(); });
76  FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
77  FPM.run(F, FAM);
78 }
79 
83 }
84 
85 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
86  std::vector<fuzzerop::OpDescriptor> Ops;
93  return Ops;
94 }
95 
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 
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.
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  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 
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.
171 }
172 
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 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:80
LLVMContext & Context
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
Externally visible function.
Definition: GlobalValue.h:49
bool isTerminator() const
Definition: Instruction.h:129
void describeFuzzerControlFlowOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:71
F(f)
Basic Dead Code Elimination pass.
Definition: DCE.h:23
PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs)
Run all of the passes in this manager over the given unit of IR.
Definition: PassManager.h:482
uint64_t getWeight(size_t CurrentSize, size_t MaxSize, uint64_t CurrentWeight) override
Provide a weight to bias towards choosing this strategy for a mutation.
Definition: IRMutator.cpp:140
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:154
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
LLVMContext & getContext() const
Get the global data context.
Definition: Module.h:243
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:822
void describeFuzzerVectorOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:86
Value * newSource(BasicBlock &BB, ArrayRef< Instruction *> Insts, ArrayRef< Value *> Srcs, fuzzerop::SourcePred Pred)
Create some Value suitable as a source for some operation.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool empty() const
Definition: Module.h:594
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
Value * findOrCreateSource(BasicBlock &BB, ArrayRef< Instruction *> Insts)
Find a "source" for some operation, which will be used in one of the operation&#39;s operands.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:219
static std::vector< fuzzerop::OpDescriptor > getDefaultOps()
Definition: IRMutator.cpp:85
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void describeFuzzerFloatOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:46
ReservoirSampler< ElT, GenT > makeSampler(GenT &RandGen, RangeT &&Items)
Definition: Random.h:76
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:161
static void eliminateDeadCode(Function &F)
Definition: IRMutator.cpp:71
static FunctionType * get(Type *Result, ArrayRef< Type *> Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:297
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
self_iterator getIterator()
Definition: ilist_node.h:82
void describeFuzzerPointerOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:76
size_t size() const
Definition: SmallVector.h:53
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:575
void connectToSink(BasicBlock &BB, ArrayRef< Instruction *> Insts, Value *V)
Find a viable user for V in Insts, which should all be contained in BB.
iterator end()
Definition: BasicBlock.h:265
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
static SourcePred onlyType(Type *Only)
Definition: OpDescriptor.h:96
void describeFuzzerIntOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Getters for the default sets of operations, per general category.
Definition: Operations.cpp:19
static void createEmptyFunction(Module &M)
Definition: IRMutator.cpp:26
virtual void mutate(Module &M, RandomIRBuilder &IB)
Definition: IRMutator.cpp:36
void describeFuzzerAggregateOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:80
void mutateModule(Module &M, int Seed, size_t CurSize, size_t MaxSize)
Definition: IRMutator.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
A description of some operation we can build while fuzzing IR.
Definition: OpDescriptor.h:90
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:412
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
static cl::opt< unsigned long long > Seed("rng-seed", cl::value_desc("seed"), cl::Hidden, cl::desc("Seed for the random number generator"), cl::init(0))
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
void addPass(PassT Pass)
Definition: PassManager.h:542
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:331
const BasicBlock * getParent() const
Definition: Instruction.h:67