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
15using namespace llvm;
16using namespace fuzzerop;
17
18void 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
45void 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
70void llvm::describeFuzzerControlFlowOps(
71    std::vector<fuzzerop::OpDescriptor> &Ops) {
72  Ops.push_back(splitBlockDescriptor(1));
73}
74
75void llvm::describeFuzzerPointerOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
76  Ops.push_back(gepDescriptor(1));
77}
78
79void llvm::describeFuzzerAggregateOps(
80    std::vector<fuzzerop::OpDescriptor> &Ops) {
81  Ops.push_back(extractValueDescriptor(1));
82  Ops.push_back(insertValueDescriptor(1));
83}
84
85void 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
91OpDescriptor 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
123OpDescriptor 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
140OpDescriptor 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
170OpDescriptor llvm::fuzzerop::gepDescriptor(unsigned Weight) {
171  auto buildGEP = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
172    Type *Ty = cast<PointerType>(Srcs[0]->getType())->getElementType();
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
182static 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
189static 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
211OpDescriptor 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
221static 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
245static SourcePred validInsertValueIndex() {
246  auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
247    auto *CTy = cast<CompositeType>(Cur[0]->getType());
248    if (auto *CI = dyn_cast<ConstantInt>(V))
249      if (CI->getBitWidth() == 32 &&
250          CTy->getTypeAtIndex(CI->getZExtValue()) == Cur[1]->getType())
251        return true;
252    return false;
253  };
254  auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
255    std::vector<Constant *> Result;
256    auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
257    auto *CTy = cast<CompositeType>(Cur[0]->getType());
258    for (int I = 0, E = getAggregateNumElements(CTy); I < E; ++I)
259      if (CTy->getTypeAtIndex(I) == Cur[1]->getType())
260        Result.push_back(ConstantInt::get(Int32Ty, I));
261    return Result;
262  };
263  return {Pred, Make};
264}
265
266OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) {
267  auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
268    // TODO: It's pretty inefficient to shuffle this all through constants.
269    unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue();
270    return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", Inst);
271  };
272  return {
273      Weight,
274      {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()},
275      buildInsert};
276}
277
278OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) {
279  auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
280    return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", Inst);
281  };
282  // TODO: Try to avoid undefined accesses.
283  return {Weight, {anyVectorType(), anyIntType()}, buildExtract};
284}
285
286OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) {
287  auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
288    return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", Inst);
289  };
290    // TODO: Try to avoid undefined accesses.
291  return {Weight,
292          {anyVectorType(), matchScalarOfFirstType(), anyIntType()},
293          buildInsert};
294}
295
296static SourcePred validShuffleVectorIndex() {
297  auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
298    return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V);
299  };
300  auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
301    auto *FirstTy = cast<VectorType>(Cur[0]->getType());
302    auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
303    // TODO: It's straighforward to make up reasonable values, but listing them
304    // exhaustively would be insane. Come up with a couple of sensible ones.
305    return std::vector<Constant *>{
306        UndefValue::get(VectorType::get(Int32Ty, FirstTy->getNumElements()))};
307  };
308  return {Pred, Make};
309}
310
311OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) {
312  auto buildShuffle = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
313    return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", Inst);
314  };
315  return {Weight,
316          {anyVectorType(), matchFirstType(), validShuffleVectorIndex()},
317          buildShuffle};
318}
319