lib/FuzzMutate/Operations.cpp

   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 = 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
 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     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
 266 OpDescriptor 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
 278 OpDescriptor 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
 286 OpDescriptor 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
 296 static 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
 311 OpDescriptor 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 }