LLVM  6.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 
13 #include "llvm/FuzzMutate/Random.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"
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.
28  /*isVarArg=*/false),
30  BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
31  ReturnInst::Create(Context, BB);
32 }
33 
35  if (M.empty())
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 
46  mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
47 }
48 
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) {
71  FPM.addPass(DCEPass());
73  FAM.registerPass([&] { return TargetLibraryAnalysis(); });
74  FPM.run(F, FAM);
75 }
76 
80 }
81 
82 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
83  std::vector<fuzzerop::OpDescriptor> Ops;
90  return Ops;
91 }
92 
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 
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.
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 
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.
155 }
156 
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 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:77
LLVMContext & Context
static cl::opt< unsigned long long > Seed("rng-seed", cl::value_desc("seed"), cl::desc("Seed for the random number generator"), cl::init(0))
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:115
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:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
Externally visible function.
Definition: GlobalValue.h:49
bool isTerminator() const
Definition: Instruction.h:128
void describeFuzzerControlFlowOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:71
F(f)
Basic Dead Code Elimination pass.
Definition: DCE.h:23
std::function< Value *(ArrayRef< Value * >, Instruction *)> BuilderFunc
Definition: OpDescriptor.h:92
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:444
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:130
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:144
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:237
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:739
void describeFuzzerVectorOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:86
virtual void mutate(BasicBlock &BB, RandomIRBuilder &IB)
Definition: IRMutator.cpp:49
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:581
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
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.
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:200
static std::vector< fuzzerop::OpDescriptor > getDefaultOps()
Definition: IRMutator.cpp:82
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:69
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:101
self_iterator getIterator()
Definition: ilist_node.h:82
void describeFuzzerPointerOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:76
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:254
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
Module.h This file contains the declarations for the Module class.
static SourcePred onlyType(Type *Only)
Definition: OpDescriptor.h:95
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:24
virtual void mutate(Module &M, RandomIRBuilder &IB)
Definition: IRMutator.cpp:34
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:53
#define I(x, y, z)
Definition: MD5.cpp:58
A description of some operation we can build while fuzzing IR.
Definition: OpDescriptor.h:89
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:286
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
inst_range instructions(Function *F)
Definition: InstIterator.h:134
A container for analyses that lazily runs them and caches their results.
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, const Twine &N="", Module *M=nullptr)
Definition: Function.h:136
void addPass(PassT Pass)
Definition: PassManager.h:485
SmallVector< SourcePred, 2 > SourcePreds
Definition: OpDescriptor.h:91
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:331
const BasicBlock * getParent() const
Definition: Instruction.h:66