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