LLVM  13.0.0git
IRMutator.cpp
Go to the documentation of this file.
1 //===-- IRMutator.cpp -----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 #include "llvm/ADT/Optional.h"
13 #include "llvm/FuzzMutate/Random.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Function.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/Module.h"
20 #include "llvm/Support/Debug.h"
22 
23 using namespace llvm;
24 
25 static void createEmptyFunction(Module &M) {
26  // TODO: Some arguments and a return value would probably be more interesting.
27  LLVMContext &Context = M.getContext();
29  /*isVarArg=*/false),
33 }
34 
36  if (M.empty())
38 
39  auto RS = makeSampler<Function *>(IB.Rand);
40  for (Function &F : M)
41  if (!F.isDeclaration())
42  RS.sample(&F, /*Weight=*/1);
43  mutate(*RS.getSelection(), IB);
44 }
45 
47  mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
48 }
49 
51  mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
52 }
53 
54 void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
55  size_t MaxSize) {
56  std::vector<Type *> Types;
57  for (const auto &Getter : AllowedTypes)
58  Types.push_back(Getter(M.getContext()));
59  RandomIRBuilder IB(Seed, Types);
60 
61  auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
62  for (const auto &Strategy : Strategies)
63  RS.sample(Strategy.get(),
64  Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
65  auto Strategy = RS.getSelection();
66 
67  Strategy->mutate(M, IB);
68 }
69 
70 static void eliminateDeadCode(Function &F) {
72  FPM.addPass(DCEPass());
74  FAM.registerPass([&] { return TargetLibraryAnalysis(); });
75  FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
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  for (Instruction &Inst : instructions(F)) {
156  // TODO: We can't handle these instructions.
157  if (Inst.isTerminator() || Inst.isEHPad() ||
158  Inst.isSwiftError() || isa<PHINode>(Inst))
159  continue;
160 
161  RS.sample(&Inst, /*Weight=*/1);
162  }
163  if (RS.isEmpty())
164  return;
165 
166  // Delete the instruction.
167  mutate(*RS.getSelection(), IB);
168  // Clean up any dead code that's left over after removing the instruction.
170 }
171 
173  assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
174 
175  if (Inst.getType()->isVoidTy()) {
176  // Instructions with void type (ie, store) have no uses to worry about. Just
177  // erase it and move on.
178  Inst.eraseFromParent();
179  return;
180  }
181 
182  // Otherwise we need to find some other value with the right type to keep the
183  // users happy.
184  auto Pred = fuzzerop::onlyType(Inst.getType());
185  auto RS = makeSampler<Value *>(IB.Rand);
186  SmallVector<Instruction *, 32> InstsBefore;
187  BasicBlock *BB = Inst.getParent();
188  for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
189  ++I) {
190  if (Pred.matches({}, &*I))
191  RS.sample(&*I, /*Weight=*/1);
192  InstsBefore.push_back(&*I);
193  }
194  if (!RS)
195  RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
196 
197  Inst.replaceAllUsesWith(RS.getSelection());
198  Inst.eraseFromParent();
199 }
200 
202  RandomIRBuilder &IB) {
203  SmallVector<std::function<void()>, 8> Modifications;
204  CmpInst *CI = nullptr;
205  GetElementPtrInst *GEP = nullptr;
206  switch (Inst.getOpcode()) {
207  default:
208  break;
209  case Instruction::Add:
210  case Instruction::Mul:
211  case Instruction::Sub:
212  case Instruction::Shl:
213  Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(true); }),
214  Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(false); });
215  Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(true); });
216  Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(false); });
217 
218  break;
219  case Instruction::ICmp:
220  CI = cast<ICmpInst>(&Inst);
221  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_EQ); });
222  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_NE); });
223  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGT); });
224  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGE); });
225  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULT); });
226  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULE); });
227  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGT); });
228  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGE); });
229  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLT); });
230  Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLE); });
231  break;
232  case Instruction::GetElementPtr:
233  GEP = cast<GetElementPtrInst>(&Inst);
234  Modifications.push_back([GEP]() { GEP->setIsInBounds(true); });
235  Modifications.push_back([GEP]() { GEP->setIsInBounds(false); });
236  break;
237  }
238 
239  auto RS = makeSampler(IB.Rand, Modifications);
240  if (RS)
241  RS.getSelection()();
242 }
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
IRMutator.h
llvm::DCEPass
Basic Dead Code Elimination pass.
Definition: DCE.h:22
llvm::RandomIRBuilder::findOrCreateSource
Value * findOrCreateSource(BasicBlock &BB, ArrayRef< Instruction * > Insts)
Find a "source" for some operation, which will be used in one of the operation's operands.
Definition: RandomIRBuilder.cpp:21
llvm
Definition: AllocatorList.h:23
createEmptyFunction
static void createEmptyFunction(Module &M)
Definition: IRMutator.cpp:25
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
Optional.h
InstIterator.h
llvm::Function
Definition: Function.h:61
llvm::InstDeleterIRStrategy::getWeight
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
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
llvm::FunctionType::get
static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)
This static method is the primary way of constructing a FunctionType.
Definition: Type.cpp:321
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:749
Module.h
llvm::InstModificationIRStrategy::mutate
void mutate(Instruction &Inst, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:201
llvm::Instruction::setHasNoUnsignedWrap
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:124
llvm::Optional
Definition: APInt.h:33
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:752
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Context
LLVMContext & Context
Definition: NVVMIntrRange.cpp:66
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::describeFuzzerPointerOps
void describeFuzzerPointerOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:75
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::Instruction::setHasNoSignedWrap
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:128
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:748
IP
Definition: NVPTXLowerArgs.cpp:166
TargetLibraryInfo.h
llvm::fuzzerop::OpDescriptor
A description of some operation we can build while fuzzing IR.
Definition: OpDescriptor.h:89
llvm::Instruction
Definition: Instruction.h:45
llvm::InjectorIRStrategy::mutate
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:79
llvm::describeFuzzerIntOps
void describeFuzzerIntOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Getters for the default sets of operations, per general category.
Definition: Operations.cpp:18
llvm::None
const NoneType None
Definition: None.h:23
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
RandomIRBuilder.h
BasicBlock.h
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
llvm::InstDeleterIRStrategy::mutate
void mutate(Function &F, RandomIRBuilder &IB) override
Definition: IRMutator.cpp:153
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:931
llvm::RandomIRBuilder::connectToSink
void connectToSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Find a viable user for V in Insts, which should all be contained in BB.
Definition: RandomIRBuilder.cpp:95
llvm::Function::Create
static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)
Definition: Function.h:137
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:746
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:751
llvm::make_pointer_range
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
Definition: iterator.h:340
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:747
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:517
llvm::BasicBlock::Create
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::make_filter_range
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:486
Operations.h
llvm::RandomIRBuilder
Definition: RandomIRBuilder.h:25
llvm::InjectorIRStrategy::getDefaultOps
static std::vector< fuzzerop::OpDescriptor > getDefaultOps()
Definition: IRMutator.cpp:84
llvm::describeFuzzerControlFlowOps
void describeFuzzerControlFlowOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:70
llvm::PassManager< Function >
llvm::makeSampler
ReservoirSampler< ElT, GenT > makeSampler(GenT &RandGen, RangeT &&Items)
Definition: Random.h:75
Random.h
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::RandomIRBuilder::Rand
RandomEngine Rand
Definition: RandomIRBuilder.h:26
Function.h
llvm::ReturnInst::Create
static ReturnInst * Create(LLVMContext &C, Value *retVal=nullptr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:2980
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:750
llvm::AnalysisManager::registerPass
bool registerPass(PassBuilderT &&PassBuilder)
Register an analysis pass with the manager.
Definition: PassManager.h:831
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::CmpInst::setPredicate
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:802
llvm::PassManager::run
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:485
llvm::RandomIRBuilder::newSource
Value * newSource(BasicBlock &BB, ArrayRef< Instruction * > Insts, ArrayRef< Value * > Srcs, fuzzerop::SourcePred Pred)
Create some Value suitable as a source for some operation.
Definition: RandomIRBuilder.cpp:41
llvm::fuzzerop::onlyType
static SourcePred onlyType(Type *Only)
Definition: OpDescriptor.h:95
llvm::IRMutationStrategy::mutate
virtual void mutate(Module &M, RandomIRBuilder &IB)
Definition: IRMutator.cpp:35
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:476
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
Seed
static cl::opt< uint64_t > Seed("rng-seed", cl::value_desc("seed"), cl::Hidden, cl::desc("Seed for the random number generator"), cl::init(0))
llvm::Type::getVoidTy
static Type * getVoidTy(LLVMContext &C)
Definition: Type.cpp:180
llvm::describeFuzzerVectorOps
void describeFuzzerVectorOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:85
Instructions.h
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:745
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::IRMutator::mutateModule
void mutateModule(Module &M, int Seed, size_t CurSize, size_t MaxSize)
Definition: IRMutator.cpp:54
eliminateDeadCode
static void eliminateDeadCode(Function &F)
Definition: IRMutator.cpp:70
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::PassInstrumentationAnalysis
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:589
DCE.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::describeFuzzerFloatOps
void describeFuzzerFloatOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:45
llvm::describeFuzzerAggregateOps
void describeFuzzerAggregateOps(std::vector< fuzzerop::OpDescriptor > &Ops)
Definition: Operations.cpp:79
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
llvm::PassManager::addPass
std::enable_if_t<!std::is_same< PassT, PassManager >::value > addPass(PassT Pass)
Definition: PassManager.h:542