1 //===-- RandomIRBuilder.cpp -----------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 #include "llvm/FuzzMutate/RandomIRBuilder.h"
10 #include "llvm/ADT/STLExtras.h"
11 #include "llvm/FuzzMutate/Random.h"
12 #include "llvm/IR/BasicBlock.h"
13 #include "llvm/IR/Constants.h"
14 #include "llvm/IR/Function.h"
15 #include "llvm/IR/Instructions.h"
16 #include "llvm/IR/IntrinsicInst.h"
19 using namespace fuzzerop
;
21 Value
*RandomIRBuilder::findOrCreateSource(BasicBlock
&BB
,
22 ArrayRef
<Instruction
*> Insts
) {
23 return findOrCreateSource(BB
, Insts
, {}, anyType());
26 Value
*RandomIRBuilder::findOrCreateSource(BasicBlock
&BB
,
27 ArrayRef
<Instruction
*> Insts
,
28 ArrayRef
<Value
*> Srcs
,
30 auto MatchesPred
= [&Srcs
, &Pred
](Instruction
*Inst
) {
31 return Pred
.matches(Srcs
, Inst
);
33 auto RS
= makeSampler(Rand
, make_filter_range(Insts
, MatchesPred
));
34 // Also consider choosing no source, meaning we want a new one.
35 RS
.sample(nullptr, /*Weight=*/1);
36 if (Instruction
*Src
= RS
.getSelection())
38 return newSource(BB
, Insts
, Srcs
, Pred
);
41 Value
*RandomIRBuilder::newSource(BasicBlock
&BB
, ArrayRef
<Instruction
*> Insts
,
42 ArrayRef
<Value
*> Srcs
, SourcePred Pred
) {
43 // Generate some constants to choose from.
44 auto RS
= makeSampler
<Value
*>(Rand
);
45 RS
.sample(Pred
.generate(Srcs
, KnownTypes
));
47 // If we can find a pointer to load from, use it half the time.
48 Value
*Ptr
= findPointer(BB
, Insts
, Srcs
, Pred
);
50 // Create load from the chosen pointer
51 auto IP
= BB
.getFirstInsertionPt();
52 if (auto *I
= dyn_cast
<Instruction
>(Ptr
)) {
53 IP
= ++I
->getIterator();
54 assert(IP
!= BB
.end() && "guaranteed by the findPointer");
56 auto *NewLoad
= new LoadInst(
57 cast
<PointerType
>(Ptr
->getType())->getElementType(), Ptr
, "L", &*IP
);
59 // Only sample this load if it really matches the descriptor
60 if (Pred
.matches(Srcs
, NewLoad
))
61 RS
.sample(NewLoad
, RS
.totalWeight());
63 NewLoad
->eraseFromParent();
66 assert(!RS
.isEmpty() && "Failed to generate sources");
67 return RS
.getSelection();
70 static bool isCompatibleReplacement(const Instruction
*I
, const Use
&Operand
,
71 const Value
*Replacement
) {
72 if (Operand
->getType() != Replacement
->getType())
74 switch (I
->getOpcode()) {
75 case Instruction::GetElementPtr
:
76 case Instruction::ExtractElement
:
77 case Instruction::ExtractValue
:
78 // TODO: We could potentially validate these, but for now just leave indices
80 if (Operand
.getOperandNo() >= 1)
83 case Instruction::InsertValue
:
84 case Instruction::InsertElement
:
85 case Instruction::ShuffleVector
:
86 if (Operand
.getOperandNo() >= 2)
95 void RandomIRBuilder::connectToSink(BasicBlock
&BB
,
96 ArrayRef
<Instruction
*> Insts
, Value
*V
) {
97 auto RS
= makeSampler
<Use
*>(Rand
);
98 for (auto &I
: Insts
) {
99 if (isa
<IntrinsicInst
>(I
))
100 // TODO: Replacing operands of intrinsics would be interesting, but
101 // there's no easy way to verify that a given replacement is valid given
102 // that intrinsics can impose arbitrary constraints.
104 for (Use
&U
: I
->operands())
105 if (isCompatibleReplacement(I
, U
, V
))
108 // Also consider choosing no sink, meaning we want a new one.
109 RS
.sample(nullptr, /*Weight=*/1);
111 if (Use
*Sink
= RS
.getSelection()) {
112 User
*U
= Sink
->getUser();
113 unsigned OpNo
= Sink
->getOperandNo();
114 U
->setOperand(OpNo
, V
);
117 newSink(BB
, Insts
, V
);
120 void RandomIRBuilder::newSink(BasicBlock
&BB
, ArrayRef
<Instruction
*> Insts
,
122 Value
*Ptr
= findPointer(BB
, Insts
, {V
}, matchFirstType());
124 if (uniform(Rand
, 0, 1))
125 Ptr
= new AllocaInst(V
->getType(), 0, "A", &*BB
.getFirstInsertionPt());
127 Ptr
= UndefValue::get(PointerType::get(V
->getType(), 0));
130 new StoreInst(V
, Ptr
, Insts
.back());
133 Value
*RandomIRBuilder::findPointer(BasicBlock
&BB
,
134 ArrayRef
<Instruction
*> Insts
,
135 ArrayRef
<Value
*> Srcs
, SourcePred Pred
) {
136 auto IsMatchingPtr
= [&Srcs
, &Pred
](Instruction
*Inst
) {
137 // Invoke instructions sometimes produce valid pointers but currently
138 // we can't insert loads or stores from them
139 if (Inst
->isTerminator())
142 if (auto PtrTy
= dyn_cast
<PointerType
>(Inst
->getType())) {
143 // We can never generate loads from non first class or non sized types
144 if (!PtrTy
->getElementType()->isSized() ||
145 !PtrTy
->getElementType()->isFirstClassType())
148 // TODO: Check if this is horribly expensive.
149 return Pred
.matches(Srcs
, UndefValue::get(PtrTy
->getElementType()));
153 if (auto RS
= makeSampler(Rand
, make_filter_range(Insts
, IsMatchingPtr
)))
154 return RS
.getSelection();