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
9#include "llvm/FuzzMutate/RandomIRBuilder.h"
10#include "llvm/ADT/STLExtras.h"
11#include "llvm/FuzzMutate/OpDescriptor.h"
12#include "llvm/FuzzMutate/Random.h"
13#include "llvm/IR/BasicBlock.h"
14#include "llvm/IR/Constants.h"
15#include "llvm/IR/DataLayout.h"
16#include "llvm/IR/Dominators.h"
17#include "llvm/IR/Function.h"
18#include "llvm/IR/Instructions.h"
19#include "llvm/IR/IntrinsicInst.h"
20#include "llvm/IR/Module.h"
21
22using namespace llvm;
23using namespace fuzzerop;
24
25/// Return a vector of Blocks that dominates this block, excluding current
26/// block.
27static std::vector<BasicBlock *> getDominators(BasicBlock *BB) {
28 std::vector<BasicBlock *> ret;
29 DominatorTree DT(*BB->getParent());
30 DomTreeNode *Node = DT.getNode(BB);
31 // It's possible that an orphan block is not in the dom tree. In that case we
32 // just return nothing.
33 if (!Node)
34 return ret;
35 Node = Node->getIDom();
36 while (Node && Node->getBlock()) {
37 ret.push_back(x: Node->getBlock());
38 // Get parent block.
39 Node = Node->getIDom();
40 }
41 return ret;
42}
43
44/// Return a vector of Blocks that is dominated by this block, excluding current
45/// block
46static std::vector<BasicBlock *> getDominatees(BasicBlock *BB) {
47 DominatorTree DT(*BB->getParent());
48 std::vector<BasicBlock *> ret;
49 DomTreeNode *Parent = DT.getNode(BB);
50 // It's possible that an orphan block is not in the dom tree. In that case we
51 // just return nothing.
52 if (!Parent)
53 return ret;
54 for (DomTreeNode *Child : Parent->children())
55 ret.push_back(x: Child->getBlock());
56 uint64_t Idx = 0;
57 while (Idx < ret.size()) {
58 DomTreeNode *Node = DT[ret[Idx]];
59 Idx++;
60 for (DomTreeNode *Child : Node->children())
61 ret.push_back(x: Child->getBlock());
62 }
63 return ret;
64}
65
66AllocaInst *RandomIRBuilder::createStackMemory(Function *F, Type *Ty,
67 Value *Init) {
68 /// TODO: For all Allocas, maybe allocate an array.
69 BasicBlock *EntryBB = &F->getEntryBlock();
70 DataLayout DL(F->getParent());
71 AllocaInst *Alloca = new AllocaInst(Ty, DL.getAllocaAddrSpace(), "A",
72 &*EntryBB->getFirstInsertionPt());
73 if (Init)
74 new StoreInst(Init, Alloca, Alloca->getNextNode());
75 return Alloca;
76}
77
78std::pair<GlobalVariable *, bool>
79RandomIRBuilder::findOrCreateGlobalVariable(Module *M, ArrayRef<Value *> Srcs,
80 fuzzerop::SourcePred Pred) {
81 auto MatchesPred = [&Srcs, &Pred](GlobalVariable *GV) {
82 // Can't directly compare GV's type, as it would be a pointer to the actual
83 // type.
84 return Pred.matches(Cur: Srcs, New: UndefValue::get(T: GV->getValueType()));
85 };
86 bool DidCreate = false;
87 SmallVector<GlobalVariable *, 4> GlobalVars;
88 for (GlobalVariable &GV : M->globals()) {
89 GlobalVars.push_back(Elt: &GV);
90 }
91 auto RS = makeSampler(RandGen&: Rand, Items: make_filter_range(Range&: GlobalVars, Pred: MatchesPred));
92 RS.sample(Item: nullptr, Weight: 1);
93 GlobalVariable *GV = RS.getSelection();
94 if (!GV) {
95 DidCreate = true;
96 using LinkageTypes = GlobalVariable::LinkageTypes;
97 auto TRS = makeSampler<Constant *>(RandGen&: Rand);
98 TRS.sample(Items: Pred.generate(Cur: Srcs, BaseTypes: KnownTypes));
99 Constant *Init = TRS.getSelection();
100 Type *Ty = Init->getType();
101 GV = new GlobalVariable(*M, Ty, false, LinkageTypes::ExternalLinkage, Init,
102 "G", nullptr,
103 GlobalValue::ThreadLocalMode::NotThreadLocal,
104 M->getDataLayout().getDefaultGlobalsAddressSpace());
105 }
106 return {GV, DidCreate};
107}
108
109Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
110 ArrayRef<Instruction *> Insts) {
111 return findOrCreateSource(BB, Insts, Srcs: {}, Pred: anyType());
112}
113
114Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
115 ArrayRef<Instruction *> Insts,
116 ArrayRef<Value *> Srcs,
117 SourcePred Pred,
118 bool allowConstant) {
119 auto MatchesPred = [&Srcs, &Pred](Value *V) { return Pred.matches(Cur: Srcs, New: V); };
120 SmallVector<uint64_t, 8> SrcTys;
121 for (uint64_t i = 0; i < EndOfValueSource; i++)
122 SrcTys.push_back(Elt: i);
123 std::shuffle(first: SrcTys.begin(), last: SrcTys.end(), g&: Rand);
124 for (uint64_t SrcTy : SrcTys) {
125 switch (SrcTy) {
126 case SrcFromInstInCurBlock: {
127 auto RS = makeSampler(RandGen&: Rand, Items: make_filter_range(Range&: Insts, Pred: MatchesPred));
128 if (!RS.isEmpty()) {
129 return RS.getSelection();
130 }
131 break;
132 }
133 case FunctionArgument: {
134 Function *F = BB.getParent();
135 SmallVector<Argument *, 8> Args;
136 for (uint64_t i = 0; i < F->arg_size(); i++) {
137 Args.push_back(Elt: F->getArg(i));
138 }
139 auto RS = makeSampler(RandGen&: Rand, Items: make_filter_range(Range&: Args, Pred: MatchesPred));
140 if (!RS.isEmpty()) {
141 return RS.getSelection();
142 }
143 break;
144 }
145 case InstInDominator: {
146 auto Dominators = getDominators(BB: &BB);
147 std::shuffle(first: Dominators.begin(), last: Dominators.end(), g&: Rand);
148 for (BasicBlock *Dom : Dominators) {
149 SmallVector<Instruction *, 16> Instructions;
150 for (Instruction &I : *Dom) {
151 Instructions.push_back(Elt: &I);
152 }
153 auto RS =
154 makeSampler(RandGen&: Rand, Items: make_filter_range(Range&: Instructions, Pred: MatchesPred));
155 // Also consider choosing no source, meaning we want a new one.
156 if (!RS.isEmpty()) {
157 return RS.getSelection();
158 }
159 }
160 break;
161 }
162 case SrcFromGlobalVariable: {
163 Module *M = BB.getParent()->getParent();
164 auto [GV, DidCreate] = findOrCreateGlobalVariable(M, Srcs, Pred);
165 Type *Ty = GV->getValueType();
166 LoadInst *LoadGV = nullptr;
167 if (BB.getTerminator()) {
168 LoadGV = new LoadInst(Ty, GV, "LGV", &*BB.getFirstInsertionPt());
169 } else {
170 LoadGV = new LoadInst(Ty, GV, "LGV", &BB);
171 }
172 // Because we might be generating new values, we have to check if it
173 // matches again.
174 if (DidCreate) {
175 if (Pred.matches(Cur: Srcs, New: LoadGV)) {
176 return LoadGV;
177 }
178 LoadGV->eraseFromParent();
179 // If no one is using this GlobalVariable, delete it too.
180 if (GV->use_empty()) {
181 GV->eraseFromParent();
182 }
183 }
184 break;
185 }
186 case NewConstOrStack: {
187 return newSource(BB, Insts, Srcs, Pred, allowConstant);
188 }
189 default:
190 case EndOfValueSource: {
191 llvm_unreachable("EndOfValueSource executed");
192 }
193 }
194 }
195 llvm_unreachable("Can't find a source");
196}
197
198Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
199 ArrayRef<Value *> Srcs, SourcePred Pred,
200 bool allowConstant) {
201 // Generate some constants to choose from.
202 auto RS = makeSampler<Value *>(RandGen&: Rand);
203 RS.sample(Items: Pred.generate(Cur: Srcs, BaseTypes: KnownTypes));
204
205 // If we can find a pointer to load from, use it half the time.
206 Value *Ptr = findPointer(BB, Insts);
207 if (Ptr) {
208 // Create load from the chosen pointer
209 auto IP = BB.getFirstInsertionPt();
210 if (auto *I = dyn_cast<Instruction>(Val: Ptr)) {
211 IP = ++I->getIterator();
212 assert(IP != BB.end() && "guaranteed by the findPointer");
213 }
214 // Pick the type independently.
215 Type *AccessTy = RS.getSelection()->getType();
216 auto *NewLoad = new LoadInst(AccessTy, Ptr, "L", &*IP);
217
218 // Only sample this load if it really matches the descriptor
219 if (Pred.matches(Cur: Srcs, New: NewLoad))
220 RS.sample(Item: NewLoad, Weight: RS.totalWeight());
221 else
222 NewLoad->eraseFromParent();
223 }
224
225 Value *newSrc = RS.getSelection();
226 // Generate a stack alloca and store the constant to it if constant is not
227 // allowed, our hope is that later mutations can generate some values and
228 // store to this placeholder.
229 if (!allowConstant && isa<Constant>(Val: newSrc)) {
230 Type *Ty = newSrc->getType();
231 Function *F = BB.getParent();
232 AllocaInst *Alloca = createStackMemory(F, Ty, Init: newSrc);
233 if (BB.getTerminator()) {
234 newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", BB.getTerminator());
235 } else {
236 newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", &BB);
237 }
238 }
239 return newSrc;
240}
241
242static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
243 const Value *Replacement) {
244 unsigned int OperandNo = Operand.getOperandNo();
245 if (Operand->getType() != Replacement->getType())
246 return false;
247 switch (I->getOpcode()) {
248 case Instruction::GetElementPtr:
249 case Instruction::ExtractElement:
250 case Instruction::ExtractValue:
251 // TODO: We could potentially validate these, but for now just leave indices
252 // alone.
253 if (OperandNo >= 1)
254 return false;
255 break;
256 case Instruction::InsertValue:
257 case Instruction::InsertElement:
258 case Instruction::ShuffleVector:
259 if (OperandNo >= 2)
260 return false;
261 break;
262 // For Br/Switch, we only try to modify the 1st Operand (condition).
263 // Modify other operands, like switch case may accidently change case from
264 // ConstantInt to a register, which is illegal.
265 case Instruction::Switch:
266 case Instruction::Br:
267 if (OperandNo >= 1)
268 return false;
269 break;
270 case Instruction::Call:
271 case Instruction::Invoke:
272 case Instruction::CallBr: {
273 const Function *Callee = cast<CallBase>(Val: I)->getCalledFunction();
274 // If it's an indirect call, give up.
275 if (!Callee)
276 return false;
277 // If callee is not an intrinsic, operand 0 is the function to be called.
278 // Since we cannot assume that the replacement is a function pointer,
279 // we give up.
280 if (!Callee->getIntrinsicID() && OperandNo == 0)
281 return false;
282 return !Callee->hasParamAttribute(ArgNo: OperandNo, Kind: Attribute::ImmArg);
283 }
284 default:
285 break;
286 }
287 return true;
288}
289
290Instruction *RandomIRBuilder::connectToSink(BasicBlock &BB,
291 ArrayRef<Instruction *> Insts,
292 Value *V) {
293 SmallVector<uint64_t, 8> SinkTys;
294 for (uint64_t i = 0; i < EndOfValueSink; i++)
295 SinkTys.push_back(Elt: i);
296 std::shuffle(first: SinkTys.begin(), last: SinkTys.end(), g&: Rand);
297 auto findSinkAndConnect =
298 [this, V](ArrayRef<Instruction *> Instructions) -> Instruction * {
299 auto RS = makeSampler<Use *>(RandGen&: Rand);
300 for (auto &I : Instructions) {
301 for (Use &U : I->operands())
302 if (isCompatibleReplacement(I, Operand: U, Replacement: V))
303 RS.sample(Item: &U, Weight: 1);
304 }
305 if (!RS.isEmpty()) {
306 Use *Sink = RS.getSelection();
307 User *U = Sink->getUser();
308 unsigned OpNo = Sink->getOperandNo();
309 U->setOperand(i: OpNo, Val: V);
310 return cast<Instruction>(Val: U);
311 }
312 return nullptr;
313 };
314 Instruction *Sink = nullptr;
315 for (uint64_t SinkTy : SinkTys) {
316 switch (SinkTy) {
317 case SinkToInstInCurBlock:
318 Sink = findSinkAndConnect(Insts);
319 if (Sink)
320 return Sink;
321 break;
322 case PointersInDominator: {
323 auto Dominators = getDominators(BB: &BB);
324 std::shuffle(first: Dominators.begin(), last: Dominators.end(), g&: Rand);
325 for (BasicBlock *Dom : Dominators) {
326 for (Instruction &I : *Dom) {
327 if (isa<PointerType>(Val: I.getType()))
328 return new StoreInst(V, &I, Insts.back());
329 }
330 }
331 break;
332 }
333 case InstInDominatee: {
334 auto Dominatees = getDominatees(BB: &BB);
335 std::shuffle(first: Dominatees.begin(), last: Dominatees.end(), g&: Rand);
336 for (BasicBlock *Dominee : Dominatees) {
337 std::vector<Instruction *> Instructions;
338 for (Instruction &I : *Dominee)
339 Instructions.push_back(x: &I);
340 Sink = findSinkAndConnect(Instructions);
341 if (Sink) {
342 return Sink;
343 }
344 }
345 break;
346 }
347 case NewStore:
348 /// TODO: allocate a new stack memory.
349 return newSink(BB, Insts, V);
350 case SinkToGlobalVariable: {
351 Module *M = BB.getParent()->getParent();
352 auto [GV, DidCreate] =
353 findOrCreateGlobalVariable(M, Srcs: {}, Pred: fuzzerop::onlyType(Only: V->getType()));
354 return new StoreInst(V, GV, Insts.back());
355 }
356 case EndOfValueSink:
357 default:
358 llvm_unreachable("EndOfValueSink executed");
359 }
360 }
361 llvm_unreachable("Can't find a sink");
362}
363
364Instruction *RandomIRBuilder::newSink(BasicBlock &BB,
365 ArrayRef<Instruction *> Insts, Value *V) {
366 Value *Ptr = findPointer(BB, Insts);
367 if (!Ptr) {
368 if (uniform(Gen&: Rand, Min: 0, Max: 1)) {
369 Type *Ty = V->getType();
370 Ptr = createStackMemory(F: BB.getParent(), Ty, Init: UndefValue::get(T: Ty));
371 } else {
372 Ptr = UndefValue::get(T: PointerType::get(ElementType: V->getType(), AddressSpace: 0));
373 }
374 }
375
376 return new StoreInst(V, Ptr, Insts.back());
377}
378
379Value *RandomIRBuilder::findPointer(BasicBlock &BB,
380 ArrayRef<Instruction *> Insts) {
381 auto IsMatchingPtr = [](Instruction *Inst) {
382 // Invoke instructions sometimes produce valid pointers but currently
383 // we can't insert loads or stores from them
384 if (Inst->isTerminator())
385 return false;
386
387 return Inst->getType()->isPointerTy();
388 };
389 if (auto RS = makeSampler(RandGen&: Rand, Items: make_filter_range(Range&: Insts, Pred: IsMatchingPtr)))
390 return RS.getSelection();
391 return nullptr;
392}
393
394Type *RandomIRBuilder::randomType() {
395 uint64_t TyIdx = uniform<uint64_t>(Gen&: Rand, Min: 0, Max: KnownTypes.size() - 1);
396 return KnownTypes[TyIdx];
397}
398
399Function *RandomIRBuilder::createFunctionDeclaration(Module &M,
400 uint64_t ArgNum) {
401 Type *RetType = randomType();
402
403 SmallVector<Type *, 2> Args;
404 for (uint64_t i = 0; i < ArgNum; i++) {
405 Args.push_back(Elt: randomType());
406 }
407
408 Function *F = Function::Create(Ty: FunctionType::get(Result: RetType, Params: Args,
409 /*isVarArg=*/false),
410 Linkage: GlobalValue::ExternalLinkage, N: "f", M: &M);
411 return F;
412}
413Function *RandomIRBuilder::createFunctionDeclaration(Module &M) {
414 return createFunctionDeclaration(
415 M, ArgNum: uniform<uint64_t>(Gen&: Rand, Min: MinArgNum, Max: MaxArgNum));
416}
417
418Function *RandomIRBuilder::createFunctionDefinition(Module &M,
419 uint64_t ArgNum) {
420 Function *F = this->createFunctionDeclaration(M, ArgNum);
421
422 // TODO: Some arguments and a return value would probably be more
423 // interesting.
424 LLVMContext &Context = M.getContext();
425 DataLayout DL(&M);
426 BasicBlock *BB = BasicBlock::Create(Context, Name: "BB", Parent: F);
427 Type *RetTy = F->getReturnType();
428 if (RetTy != Type::getVoidTy(C&: Context)) {
429 Instruction *RetAlloca =
430 new AllocaInst(RetTy, DL.getAllocaAddrSpace(), "RP", BB);
431 Instruction *RetLoad = new LoadInst(RetTy, RetAlloca, "", BB);
432 ReturnInst::Create(C&: Context, retVal: RetLoad, InsertBefore: BB);
433 } else {
434 ReturnInst::Create(C&: Context, InsertAtEnd: BB);
435 }
436
437 return F;
438}
439Function *RandomIRBuilder::createFunctionDefinition(Module &M) {
440 return createFunctionDefinition(
441 M, ArgNum: uniform<uint64_t>(Gen&: Rand, Min: MinArgNum, Max: MaxArgNum));
442}
443