LLVM 17.0.0git
RandomIRBuilder.cpp
Go to the documentation of this file.
1//===-- RandomIRBuilder.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/STLExtras.h"
13#include "llvm/IR/BasicBlock.h"
14#include "llvm/IR/Constants.h"
15#include "llvm/IR/DataLayout.h"
18
19using namespace llvm;
20using namespace fuzzerop;
21
24 return findOrCreateSource(BB, Insts, {}, anyType());
25}
26
30 SourcePred Pred,
31 bool allowConstant) {
32 auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) {
33 return Pred.matches(Srcs, Inst);
34 };
35 auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred));
36 // Also consider choosing no source, meaning we want a new one.
37 RS.sample(nullptr, /*Weight=*/1);
38 if (Instruction *Src = RS.getSelection())
39 return Src;
40 return newSource(BB, Insts, Srcs, Pred, allowConstant);
41}
42
45 bool allowConstant) {
46 // Generate some constants to choose from.
47 auto RS = makeSampler<Value *>(Rand);
48 RS.sample(Pred.generate(Srcs, KnownTypes));
49
50 // If we can find a pointer to load from, use it half the time.
51 Value *Ptr = findPointer(BB, Insts, Srcs, Pred);
52 if (Ptr) {
53 // Create load from the chosen pointer
54 auto IP = BB.getFirstInsertionPt();
55 if (auto *I = dyn_cast<Instruction>(Ptr)) {
56 IP = ++I->getIterator();
57 assert(IP != BB.end() && "guaranteed by the findPointer");
58 }
59 // For opaque pointers, pick the type independently.
60 Type *AccessTy = Ptr->getType()->isOpaquePointerTy()
61 ? RS.getSelection()->getType()
62 : Ptr->getType()->getNonOpaquePointerElementType();
63 auto *NewLoad = new LoadInst(AccessTy, Ptr, "L", &*IP);
64
65 // Only sample this load if it really matches the descriptor
66 if (Pred.matches(Srcs, NewLoad))
67 RS.sample(NewLoad, RS.totalWeight());
68 else
69 NewLoad->eraseFromParent();
70 }
71
72 Value *newSrc = RS.getSelection();
73 // Generate a stack alloca and store the constant to it if constant is not
74 // allowed, our hope is that later mutations can generate some values and
75 // store to this placeholder.
76 if (!allowConstant && isa<Constant>(newSrc)) {
77 Type *Ty = newSrc->getType();
78 Function *F = BB.getParent();
79 BasicBlock *EntryBB = &F->getEntryBlock();
80 /// TODO: For all Allocas, maybe allocate an array.
82 AllocaInst *Alloca = new AllocaInst(Ty, DL.getProgramAddressSpace(), "A",
83 EntryBB->getTerminator());
84 new StoreInst(newSrc, Alloca, EntryBB->getTerminator());
85 if (BB.getTerminator()) {
86 newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", BB.getTerminator());
87 } else {
88 newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", &BB);
89 }
90 }
91 return newSrc;
92}
93
94static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
95 const Value *Replacement) {
96 unsigned int OperandNo = Operand.getOperandNo();
97 if (Operand->getType() != Replacement->getType())
98 return false;
99 switch (I->getOpcode()) {
100 case Instruction::GetElementPtr:
101 case Instruction::ExtractElement:
102 case Instruction::ExtractValue:
103 // TODO: We could potentially validate these, but for now just leave indices
104 // alone.
105 if (OperandNo >= 1)
106 return false;
107 break;
108 case Instruction::InsertValue:
109 case Instruction::InsertElement:
110 case Instruction::ShuffleVector:
111 if (OperandNo >= 2)
112 return false;
113 break;
114 // For Br/Switch, we only try to modify the 1st Operand (condition).
115 // Modify other operands, like switch case may accidently change case from
116 // ConstantInt to a register, which is illegal.
117 case Instruction::Switch:
118 case Instruction::Br:
119 if (OperandNo >= 1)
120 return false;
121 break;
122 default:
123 break;
124 }
125 return true;
126}
127
129 ArrayRef<Instruction *> Insts, Value *V) {
130 auto RS = makeSampler<Use *>(Rand);
131 for (auto &I : Insts) {
132 if (isa<IntrinsicInst>(I))
133 // TODO: Replacing operands of intrinsics would be interesting, but
134 // there's no easy way to verify that a given replacement is valid given
135 // that intrinsics can impose arbitrary constraints.
136 continue;
137 for (Use &U : I->operands())
138 if (isCompatibleReplacement(I, U, V))
139 RS.sample(&U, 1);
140 }
141 // Also consider choosing no sink, meaning we want a new one.
142 RS.sample(nullptr, /*Weight=*/1);
143
144 if (Use *Sink = RS.getSelection()) {
145 User *U = Sink->getUser();
146 unsigned OpNo = Sink->getOperandNo();
147 U->setOperand(OpNo, V);
148 return;
149 }
150 newSink(BB, Insts, V);
151}
152
154 Value *V) {
155 Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType());
156 if (!Ptr) {
157 if (uniform(Rand, 0, 1))
158 Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt());
159 else
160 Ptr = UndefValue::get(PointerType::get(V->getType(), 0));
161 }
162
163 new StoreInst(V, Ptr, Insts.back());
164}
165
168 ArrayRef<Value *> Srcs, SourcePred Pred) {
169 auto IsMatchingPtr = [&Srcs, &Pred](Instruction *Inst) {
170 // Invoke instructions sometimes produce valid pointers but currently
171 // we can't insert loads or stores from them
172 if (Inst->isTerminator())
173 return false;
174
175 if (auto *PtrTy = dyn_cast<PointerType>(Inst->getType())) {
176 if (PtrTy->isOpaque())
177 return true;
178
179 // We can never generate loads from non first class or non sized types
180 Type *ElemTy = PtrTy->getNonOpaquePointerElementType();
181 if (!ElemTy->isSized() || !ElemTy->isFirstClassType())
182 return false;
183
184 // TODO: Check if this is horribly expensive.
185 return Pred.matches(Srcs, UndefValue::get(ElemTy));
186 }
187 return false;
188 };
189 if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
190 return RS.getSelection();
191 return nullptr;
192}
193
195 uint64_t TyIdx = uniform<uint64_t>(Rand, 0, KnownTypes.size() - 1);
196 return KnownTypes[TyIdx];
197}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static bool isCompatibleReplacement(const Instruction *I, const Use &Operand, const Value *Replacement)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
const T & back() const
back - Get the last element.
Definition: ArrayRef.h:172
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
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:245
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:652
An instruction for reading from memory.
Definition: Instructions.h:177
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
An instruction for storing to memory.
Definition: Instructions.h:301
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Type * getNonOpaquePointerElementType() const
Only use this method in code that is not reachable with opaque pointers, or part of deprecated method...
Definition: Type.h:425
bool isFirstClassType() const
Return true if the type is "first class", meaning it is a valid type for a Value.
Definition: Type.h:283
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:304
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1731
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
unsigned getOperandNo() const
Return the operand # of this use in its User.
Definition: Use.cpp:31
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
A matcher/generator for finding suitable values for the next source in an operation's partially compl...
Definition: OpDescriptor.h:42
bool matches(ArrayRef< Value * > Cur, const Value *New)
Returns true if New is compatible for the argument after Cur.
Definition: OpDescriptor.h:76
std::vector< Constant * > generate(ArrayRef< Value * > Cur, ArrayRef< Type * > BaseTypes)
Generates a list of potential values for the argument after Cur.
Definition: OpDescriptor.h:81
static SourcePred matchFirstType()
Match values that have the same type as the first source.
Definition: OpDescriptor.h:194
static SourcePred anyType()
Definition: OpDescriptor.h:104
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ReservoirSampler< ElT, GenT > makeSampler(GenT &RandGen, RangeT &&Items)
Definition: Random.h:75
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:664
T uniform(GenT &Gen, T Min, T Max)
Return a uniformly distributed random value between Min and Max.
Definition: Random.h:21
SmallVector< Type *, 16 > KnownTypes
Value * findOrCreateSource(BasicBlock &BB, ArrayRef< Instruction * > Insts)
Find a "source" for some operation, which will be used in one of the operation's operands.
Value * newSource(BasicBlock &BB, ArrayRef< Instruction * > Insts, ArrayRef< Value * > Srcs, fuzzerop::SourcePred Pred, bool allowConstant=true)
Create some Value suitable as a source for some operation.
void newSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Create a user for V in BB.
Value * findPointer(BasicBlock &BB, ArrayRef< Instruction * > Insts, ArrayRef< Value * > Srcs, fuzzerop::SourcePred Pred)
void connectToSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Find a viable user for V in Insts, which should all be contained in BB.
Type * randomType()
Return a uniformly choosen type from AllowedTypes.