1 //===-- Operations.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
10 #include "llvm/FuzzMutate/Operations.h"
11 #include "llvm/IR/BasicBlock.h"
12 #include "llvm/IR/Constants.h"
13 #include "llvm/IR/Function.h"
14 #include "llvm/IR/Instructions.h"
15
16 using namespace llvm;
17 using namespace fuzzerop;
18
describeFuzzerIntOps(std::vector<fuzzerop::OpDescriptor> & Ops)19 void llvm::describeFuzzerIntOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
20 Ops.push_back(binOpDescriptor(1, Instruction::Add));
21 Ops.push_back(binOpDescriptor(1, Instruction::Sub));
22 Ops.push_back(binOpDescriptor(1, Instruction::Mul));
23 Ops.push_back(binOpDescriptor(1, Instruction::SDiv));
24 Ops.push_back(binOpDescriptor(1, Instruction::UDiv));
25 Ops.push_back(binOpDescriptor(1, Instruction::SRem));
26 Ops.push_back(binOpDescriptor(1, Instruction::URem));
27 Ops.push_back(binOpDescriptor(1, Instruction::Shl));
28 Ops.push_back(binOpDescriptor(1, Instruction::LShr));
29 Ops.push_back(binOpDescriptor(1, Instruction::AShr));
30 Ops.push_back(binOpDescriptor(1, Instruction::And));
31 Ops.push_back(binOpDescriptor(1, Instruction::Or));
32 Ops.push_back(binOpDescriptor(1, Instruction::Xor));
33
34 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_EQ));
35 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_NE));
36 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_UGT));
37 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_UGE));
38 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_ULT));
39 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_ULE));
40 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SGT));
41 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SGE));
42 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SLT));
43 Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SLE));
44 }
45
describeFuzzerFloatOps(std::vector<fuzzerop::OpDescriptor> & Ops)46 void llvm::describeFuzzerFloatOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
47 Ops.push_back(binOpDescriptor(1, Instruction::FAdd));
48 Ops.push_back(binOpDescriptor(1, Instruction::FSub));
49 Ops.push_back(binOpDescriptor(1, Instruction::FMul));
50 Ops.push_back(binOpDescriptor(1, Instruction::FDiv));
51 Ops.push_back(binOpDescriptor(1, Instruction::FRem));
52
53 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_FALSE));
54 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OEQ));
55 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OGT));
56 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OGE));
57 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OLT));
58 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OLE));
59 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ONE));
60 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ORD));
61 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UNO));
62 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UEQ));
63 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UGT));
64 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UGE));
65 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ULT));
66 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ULE));
67 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UNE));
68 Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_TRUE));
69 }
70
describeFuzzerControlFlowOps(std::vector<fuzzerop::OpDescriptor> & Ops)71 void llvm::describeFuzzerControlFlowOps(
72 std::vector<fuzzerop::OpDescriptor> &Ops) {
73 Ops.push_back(splitBlockDescriptor(1));
74 }
75
describeFuzzerPointerOps(std::vector<fuzzerop::OpDescriptor> & Ops)76 void llvm::describeFuzzerPointerOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
77 Ops.push_back(gepDescriptor(1));
78 }
79
describeFuzzerAggregateOps(std::vector<fuzzerop::OpDescriptor> & Ops)80 void llvm::describeFuzzerAggregateOps(
81 std::vector<fuzzerop::OpDescriptor> &Ops) {
82 Ops.push_back(extractValueDescriptor(1));
83 Ops.push_back(insertValueDescriptor(1));
84 }
85
describeFuzzerVectorOps(std::vector<fuzzerop::OpDescriptor> & Ops)86 void llvm::describeFuzzerVectorOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
87 Ops.push_back(extractElementDescriptor(1));
88 Ops.push_back(insertElementDescriptor(1));
89 Ops.push_back(shuffleVectorDescriptor(1));
90 }
91
binOpDescriptor(unsigned Weight,Instruction::BinaryOps Op)92 OpDescriptor llvm::fuzzerop::binOpDescriptor(unsigned Weight,
93 Instruction::BinaryOps Op) {
94 auto buildOp = [Op](ArrayRef<Value *> Srcs, Instruction *Inst) {
95 return BinaryOperator::Create(Op, Srcs[0], Srcs[1], "B", Inst);
96 };
97 switch (Op) {
98 case Instruction::Add:
99 case Instruction::Sub:
100 case Instruction::Mul:
101 case Instruction::SDiv:
102 case Instruction::UDiv:
103 case Instruction::SRem:
104 case Instruction::URem:
105 case Instruction::Shl:
106 case Instruction::LShr:
107 case Instruction::AShr:
108 case Instruction::And:
109 case Instruction::Or:
110 case Instruction::Xor:
111 return {Weight, {anyIntType(), matchFirstType()}, buildOp};
112 case Instruction::FAdd:
113 case Instruction::FSub:
114 case Instruction::FMul:
115 case Instruction::FDiv:
116 case Instruction::FRem:
117 return {Weight, {anyFloatType(), matchFirstType()}, buildOp};
118 case Instruction::BinaryOpsEnd:
119 llvm_unreachable("Value out of range of enum");
120 }
121 llvm_unreachable("Covered switch");
122 }
123
cmpOpDescriptor(unsigned Weight,Instruction::OtherOps CmpOp,CmpInst::Predicate Pred)124 OpDescriptor llvm::fuzzerop::cmpOpDescriptor(unsigned Weight,
125 Instruction::OtherOps CmpOp,
126 CmpInst::Predicate Pred) {
127 auto buildOp = [CmpOp, Pred](ArrayRef<Value *> Srcs, Instruction *Inst) {
128 return CmpInst::Create(CmpOp, Pred, Srcs[0], Srcs[1], "C", Inst);
129 };
130
131 switch (CmpOp) {
132 case Instruction::ICmp:
133 return {Weight, {anyIntType(), matchFirstType()}, buildOp};
134 case Instruction::FCmp:
135 return {Weight, {anyFloatType(), matchFirstType()}, buildOp};
136 default:
137 llvm_unreachable("CmpOp must be ICmp or FCmp");
138 }
139 }
140
splitBlockDescriptor(unsigned Weight)141 OpDescriptor llvm::fuzzerop::splitBlockDescriptor(unsigned Weight) {
142 auto buildSplitBlock = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
143 BasicBlock *Block = Inst->getParent();
144 BasicBlock *Next = Block->splitBasicBlock(Inst, "BB");
145
146 // If it was an exception handling block, we are done.
147 if (Block->isEHPad())
148 return nullptr;
149
150 // Loop back on this block by replacing the unconditional forward branch
151 // with a conditional with a backedge.
152 if (Block != &Block->getParent()->getEntryBlock()) {
153 BranchInst::Create(Block, Next, Srcs[0], Block->getTerminator());
154 Block->getTerminator()->eraseFromParent();
155
156 // We need values for each phi in the block. Since there isn't a good way
157 // to do a variable number of input values currently, we just fill them
158 // with undef.
159 for (PHINode &PHI : Block->phis())
160 PHI.addIncoming(UndefValue::get(PHI.getType()), Block);
161 }
162 return nullptr;
163 };
164 SourcePred isInt1Ty{[](ArrayRef<Value *>, const Value *V) {
165 return V->getType()->isIntegerTy(1);
166 },
167 None};
168 return {Weight, {isInt1Ty}, buildSplitBlock};
169 }
170
gepDescriptor(unsigned Weight)171 OpDescriptor llvm::fuzzerop::gepDescriptor(unsigned Weight) {
172 auto buildGEP = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
173 Type *Ty = cast<PointerType>(Srcs[0]->getType())->getElementType();
174 auto Indices = makeArrayRef(Srcs).drop_front(1);
175 return GetElementPtrInst::Create(Ty, Srcs[0], Indices, "G", Inst);
176 };
177 // TODO: Handle aggregates and vectors
178 // TODO: Support multiple indices.
179 // TODO: Try to avoid meaningless accesses.
180 return {Weight, {sizedPtrType(), anyIntType()}, buildGEP};
181 }
182
getAggregateNumElements(Type * T)183 static uint64_t getAggregateNumElements(Type *T) {
184 assert(T->isAggregateType() && "Not a struct or array");
185 if (isa<StructType>(T))
186 return T->getStructNumElements();
187 return T->getArrayNumElements();
188 }
189
validExtractValueIndex()190 static SourcePred validExtractValueIndex() {
191 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
192 if (auto *CI = dyn_cast<ConstantInt>(V))
193 if (!CI->uge(getAggregateNumElements(Cur[0]->getType())))
194 return true;
195 return false;
196 };
197 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
198 std::vector<Constant *> Result;
199 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
200 uint64_t N = getAggregateNumElements(Cur[0]->getType());
201 // Create indices at the start, end, and middle, but avoid dups.
202 Result.push_back(ConstantInt::get(Int32Ty, 0));
203 if (N > 1)
204 Result.push_back(ConstantInt::get(Int32Ty, N - 1));
205 if (N > 2)
206 Result.push_back(ConstantInt::get(Int32Ty, N / 2));
207 return Result;
208 };
209 return {Pred, Make};
210 }
211
extractValueDescriptor(unsigned Weight)212 OpDescriptor llvm::fuzzerop::extractValueDescriptor(unsigned Weight) {
213 auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
214 // TODO: It's pretty inefficient to shuffle this all through constants.
215 unsigned Idx = cast<ConstantInt>(Srcs[1])->getZExtValue();
216 return ExtractValueInst::Create(Srcs[0], {Idx}, "E", Inst);
217 };
218 // TODO: Should we handle multiple indices?
219 return {Weight, {anyAggregateType(), validExtractValueIndex()}, buildExtract};
220 }
221
matchScalarInAggregate()222 static SourcePred matchScalarInAggregate() {
223 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
224 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType()))
225 return V->getType() == ArrayT->getElementType();
226
227 auto *STy = cast<StructType>(Cur[0]->getType());
228 for (int I = 0, E = STy->getNumElements(); I < E; ++I)
229 if (STy->getTypeAtIndex(I) == V->getType())
230 return true;
231 return false;
232 };
233 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *>) {
234 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType()))
235 return makeConstantsWithType(ArrayT->getElementType());
236
237 std::vector<Constant *> Result;
238 auto *STy = cast<StructType>(Cur[0]->getType());
239 for (int I = 0, E = STy->getNumElements(); I < E; ++I)
240 makeConstantsWithType(STy->getTypeAtIndex(I), Result);
241 return Result;
242 };
243 return {Pred, Make};
244 }
245
validInsertValueIndex()246 static SourcePred validInsertValueIndex() {
247 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
248 auto *CTy = cast<CompositeType>(Cur[0]->getType());
249 if (auto *CI = dyn_cast<ConstantInt>(V))
250 if (CI->getBitWidth() == 32 &&
251 CTy->getTypeAtIndex(CI->getZExtValue()) == Cur[1]->getType())
252 return true;
253 return false;
254 };
255 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
256 std::vector<Constant *> Result;
257 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
258 auto *CTy = cast<CompositeType>(Cur[0]->getType());
259 for (int I = 0, E = getAggregateNumElements(CTy); I < E; ++I)
260 if (CTy->getTypeAtIndex(I) == Cur[1]->getType())
261 Result.push_back(ConstantInt::get(Int32Ty, I));
262 return Result;
263 };
264 return {Pred, Make};
265 }
266
insertValueDescriptor(unsigned Weight)267 OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) {
268 auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
269 // TODO: It's pretty inefficient to shuffle this all through constants.
270 unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue();
271 return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", Inst);
272 };
273 return {
274 Weight,
275 {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()},
276 buildInsert};
277 }
278
extractElementDescriptor(unsigned Weight)279 OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) {
280 auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
281 return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", Inst);
282 };
283 // TODO: Try to avoid undefined accesses.
284 return {Weight, {anyVectorType(), anyIntType()}, buildExtract};
285 }
286
insertElementDescriptor(unsigned Weight)287 OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) {
288 auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
289 return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", Inst);
290 };
291 // TODO: Try to avoid undefined accesses.
292 return {Weight,
293 {anyVectorType(), matchScalarOfFirstType(), anyIntType()},
294 buildInsert};
295 }
296
validShuffleVectorIndex()297 static SourcePred validShuffleVectorIndex() {
298 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
299 return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V);
300 };
301 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
302 auto *FirstTy = cast<VectorType>(Cur[0]->getType());
303 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
304 // TODO: It's straighforward to make up reasonable values, but listing them
305 // exhaustively would be insane. Come up with a couple of sensible ones.
306 return std::vector<Constant *>{
307 UndefValue::get(VectorType::get(Int32Ty, FirstTy->getNumElements()))};
308 };
309 return {Pred, Make};
310 }
311
shuffleVectorDescriptor(unsigned Weight)312 OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) {
313 auto buildShuffle = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
314 return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", Inst);
315 };
316 return {Weight,
317 {anyVectorType(), matchFirstType(), validShuffleVectorIndex()},
318 buildShuffle};
319 }
320