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                       None};
167   return {Weight, {isInt1Ty}, buildSplitBlock};
168 }
169 
170 OpDescriptor llvm::fuzzerop::gepDescriptor(unsigned Weight) {
171   auto buildGEP = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
172     Type *Ty = Srcs[0]->getType()->getPointerElementType();
173     auto Indices = makeArrayRef(Srcs).drop_front(1);
174     return GetElementPtrInst::Create(Ty, Srcs[0], Indices, "G", Inst);
175   };
176   // TODO: Handle aggregates and vectors
177   // TODO: Support multiple indices.
178   // TODO: Try to avoid meaningless accesses.
179   return {Weight, {sizedPtrType(), anyIntType()}, buildGEP};
180 }
181 
182 static uint64_t getAggregateNumElements(Type *T) {
183   assert(T->isAggregateType() && "Not a struct or array");
184   if (isa<StructType>(T))
185     return T->getStructNumElements();
186   return T->getArrayNumElements();
187 }
188 
189 static SourcePred validExtractValueIndex() {
190   auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
191     if (auto *CI = dyn_cast<ConstantInt>(V))
192       if (!CI->uge(getAggregateNumElements(Cur[0]->getType())))
193         return true;
194     return false;
195   };
196   auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
197     std::vector<Constant *> Result;
198     auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
199     uint64_t N = getAggregateNumElements(Cur[0]->getType());
200     // Create indices at the start, end, and middle, but avoid dups.
201     Result.push_back(ConstantInt::get(Int32Ty, 0));
202     if (N > 1)
203       Result.push_back(ConstantInt::get(Int32Ty, N - 1));
204     if (N > 2)
205       Result.push_back(ConstantInt::get(Int32Ty, N / 2));
206     return Result;
207   };
208   return {Pred, Make};
209 }
210 
211 OpDescriptor llvm::fuzzerop::extractValueDescriptor(unsigned Weight) {
212   auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
213     // TODO: It's pretty inefficient to shuffle this all through constants.
214     unsigned Idx = cast<ConstantInt>(Srcs[1])->getZExtValue();
215     return ExtractValueInst::Create(Srcs[0], {Idx}, "E", Inst);
216   };
217   // TODO: Should we handle multiple indices?
218   return {Weight, {anyAggregateType(), validExtractValueIndex()}, buildExtract};
219 }
220 
221 static SourcePred matchScalarInAggregate() {
222   auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
223     if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType()))
224       return V->getType() == ArrayT->getElementType();
225 
226     auto *STy = cast<StructType>(Cur[0]->getType());
227     for (int I = 0, E = STy->getNumElements(); I < E; ++I)
228       if (STy->getTypeAtIndex(I) == V->getType())
229         return true;
230     return false;
231   };
232   auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *>) {
233     if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType()))
234       return makeConstantsWithType(ArrayT->getElementType());
235 
236     std::vector<Constant *> Result;
237     auto *STy = cast<StructType>(Cur[0]->getType());
238     for (int I = 0, E = STy->getNumElements(); I < E; ++I)
239       makeConstantsWithType(STy->getTypeAtIndex(I), Result);
240     return Result;
241   };
242   return {Pred, Make};
243 }
244 
245 static SourcePred validInsertValueIndex() {
246   auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
247     if (auto *CI = dyn_cast<ConstantInt>(V))
248       if (CI->getBitWidth() == 32) {
249         Type *Indexed = ExtractValueInst::getIndexedType(Cur[0]->getType(),
250                                                          CI->getZExtValue());
251         return Indexed == Cur[1]->getType();
252       }
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 *BaseTy = Cur[0]->getType();
259     int I = 0;
260     while (Type *Indexed = ExtractValueInst::getIndexedType(BaseTy, I)) {
261       if (Indexed == Cur[1]->getType())
262         Result.push_back(ConstantInt::get(Int32Ty, I));
263       ++I;
264     }
265     return Result;
266   };
267   return {Pred, Make};
268 }
269 
270 OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) {
271   auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
272     // TODO: It's pretty inefficient to shuffle this all through constants.
273     unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue();
274     return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", Inst);
275   };
276   return {
277       Weight,
278       {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()},
279       buildInsert};
280 }
281 
282 OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) {
283   auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
284     return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", Inst);
285   };
286   // TODO: Try to avoid undefined accesses.
287   return {Weight, {anyVectorType(), anyIntType()}, buildExtract};
288 }
289 
290 OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) {
291   auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
292     return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", Inst);
293   };
294     // TODO: Try to avoid undefined accesses.
295   return {Weight,
296           {anyVectorType(), matchScalarOfFirstType(), anyIntType()},
297           buildInsert};
298 }
299 
300 static SourcePred validShuffleVectorIndex() {
301   auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
302     return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V);
303   };
304   auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
305     auto *FirstTy = cast<FixedVectorType>(Cur[0]->getType());
306     auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
307     // TODO: It's straighforward to make up reasonable values, but listing them
308     // exhaustively would be insane. Come up with a couple of sensible ones.
309     return std::vector<Constant *>{UndefValue::get(
310         FixedVectorType::get(Int32Ty, FirstTy->getNumElements()))};
311   };
312   return {Pred, Make};
313 }
314 
315 OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) {
316   auto buildShuffle = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
317     return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", Inst);
318   };
319   return {Weight,
320           {anyVectorType(), matchFirstType(), validShuffleVectorIndex()},
321           buildShuffle};
322 }
323