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 
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 
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 
71 void llvm::describeFuzzerControlFlowOps(
72     std::vector<fuzzerop::OpDescriptor> &Ops) {
73   Ops.push_back(splitBlockDescriptor(1));
74 }
75 
76 void llvm::describeFuzzerPointerOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
77   Ops.push_back(gepDescriptor(1));
78 }
79 
80 void llvm::describeFuzzerAggregateOps(
81     std::vector<fuzzerop::OpDescriptor> &Ops) {
82   Ops.push_back(extractValueDescriptor(1));
83   Ops.push_back(insertValueDescriptor(1));
84 }
85 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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