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