LLVM  7.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  FPM.run(F, FAM);
77 }
78 
82 }
83 
84 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
85  std::vector<fuzzerop::OpDescriptor> Ops;
92  return Ops;
93 }
94 
96 InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
97  auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
98  return Op.SourcePreds[0].matches({}, Src);
99  };
100  auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
101  if (RS.isEmpty())
102  return None;
103  return *RS;
104 }
105 
108  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
109  Insts.push_back(&*I);
110  if (Insts.size() < 1)
111  return;
112 
113  // Choose an insertion point for our new instruction.
114  size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
115 
116  auto InstsBefore = makeArrayRef(Insts).slice(0, IP);
117  auto InstsAfter = makeArrayRef(Insts).slice(IP);
118 
119  // Choose a source, which will be used to constrain the operation selection.
121  Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore));
122 
123  // Choose an operation that's constrained to be valid for the type of the
124  // source, collect any other sources it needs, and then build it.
125  auto OpDesc = chooseOperation(Srcs[0], IB);
126  // Bail if no operation was found
127  if (!OpDesc)
128  return;
129 
130  for (const auto &Pred : makeArrayRef(OpDesc->SourcePreds).slice(1))
131  Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
132 
133  if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) {
134  // Find a sink and wire up the results of the operation.
135  IB.connectToSink(BB, InstsAfter, Op);
136  }
137 }
138 
139 uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize,
140  uint64_t CurrentWeight) {
141  // If we have less than 200 bytes, panic and try to always delete.
142  if (CurrentSize > MaxSize - 200)
143  return CurrentWeight ? CurrentWeight * 100 : 1;
144  // Draw a line starting from when we only have 1k left and increasing linearly
145  // to double the current weight.
146  int Line = (-2 * CurrentWeight) * (MaxSize - CurrentSize + 1000);
147  // Clamp negative weights to zero.
148  if (Line < 0)
149  return 0;
150  return Line;
151 }
152 
154  auto RS = makeSampler<Instruction *>(IB.Rand);
155  // Avoid terminators so we don't have to worry about keeping the CFG coherent.
156  for (Instruction &Inst : instructions(F))
157  if (!Inst.isTerminator())
158  RS.sample(&Inst, /*Weight=*/1);
159  if (RS.isEmpty())
160  return;
161 
162  // Delete the instruction.
163  mutate(*RS.getSelection(), IB);
164  // Clean up any dead code that's left over after removing the instruction.
166 }
167 
169  assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
170 
171  if (Inst.getType()->isVoidTy()) {
172  // Instructions with void type (ie, store) have no uses to worry about. Just
173  // erase it and move on.
174  Inst.eraseFromParent();
175  return;
176  }
177 
178  // Otherwise we need to find some other value with the right type to keep the
179  // users happy.
180  auto Pred = fuzzerop::onlyType(Inst.getType());
181  auto RS = makeSampler<Value *>(IB.Rand);
182  SmallVector<Instruction *, 32> InstsBefore;
183  BasicBlock *BB = Inst.getParent();
184  for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
185  ++I) {
186  if (Pred.matches({}, &*I))
187  RS.sample(&*I, /*Weight=*/1);
188  InstsBefore.push_back(&*I);
189  }
190  if (!RS)
191  RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
192 
193  Inst.replaceAllUsesWith(RS.getSelection());
194 }
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:79
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: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: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: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:139
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:153
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
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: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.
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:84
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: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: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:862
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:333
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.
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
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:331
const BasicBlock * getParent() const
Definition: Instruction.h:67