lib/FuzzMutate/Operations.cpp

   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 }