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::describeFuzzerUnaryOperations( 71 std::vector<fuzzerop::OpDescriptor> &Ops) { 72 Ops.push_back(fnegDescriptor(1)); 73 } 74 75 void llvm::describeFuzzerControlFlowOps( 76 std::vector<fuzzerop::OpDescriptor> &Ops) { 77 Ops.push_back(splitBlockDescriptor(1)); 78 } 79 80 void llvm::describeFuzzerOtherOps(std::vector<fuzzerop::OpDescriptor> &Ops) { 81 Ops.push_back(selectDescriptor(1)); 82 } 83 84 void llvm::describeFuzzerPointerOps(std::vector<fuzzerop::OpDescriptor> &Ops) { 85 Ops.push_back(gepDescriptor(1)); 86 } 87 88 void llvm::describeFuzzerAggregateOps( 89 std::vector<fuzzerop::OpDescriptor> &Ops) { 90 Ops.push_back(extractValueDescriptor(1)); 91 Ops.push_back(insertValueDescriptor(1)); 92 } 93 94 void llvm::describeFuzzerVectorOps(std::vector<fuzzerop::OpDescriptor> &Ops) { 95 Ops.push_back(extractElementDescriptor(1)); 96 Ops.push_back(insertElementDescriptor(1)); 97 Ops.push_back(shuffleVectorDescriptor(1)); 98 } 99 100 OpDescriptor llvm::fuzzerop::selectDescriptor(unsigned Weight) { 101 auto buildOp = [](ArrayRef<Value *> Srcs, BasicBlock::iterator InsertPt) { 102 return SelectInst::Create(Srcs[0], Srcs[1], Srcs[2], "S", InsertPt); 103 }; 104 return {Weight, 105 {boolOrVecBoolType(), matchFirstLengthWAnyType(), matchSecondType()}, 106 buildOp}; 107 } 108 109 OpDescriptor llvm::fuzzerop::fnegDescriptor(unsigned Weight) { 110 auto buildOp = [](ArrayRef<Value *> Srcs, BasicBlock::iterator InsertPt) { 111 return UnaryOperator::Create(Instruction::FNeg, Srcs[0], "F", InsertPt); 112 }; 113 return {Weight, {anyFloatOrVecFloatType()}, buildOp}; 114 } 115 116 OpDescriptor llvm::fuzzerop::binOpDescriptor(unsigned Weight, 117 Instruction::BinaryOps Op) { 118 auto buildOp = [Op](ArrayRef<Value *> Srcs, BasicBlock::iterator InsertPt) { 119 return BinaryOperator::Create(Op, Srcs[0], Srcs[1], "B", InsertPt); 120 }; 121 switch (Op) { 122 case Instruction::Add: 123 case Instruction::Sub: 124 case Instruction::Mul: 125 case Instruction::SDiv: 126 case Instruction::UDiv: 127 case Instruction::SRem: 128 case Instruction::URem: 129 case Instruction::Shl: 130 case Instruction::LShr: 131 case Instruction::AShr: 132 case Instruction::And: 133 case Instruction::Or: 134 case Instruction::Xor: 135 return {Weight, {anyIntOrVecIntType(), matchFirstType()}, buildOp}; 136 case Instruction::FAdd: 137 case Instruction::FSub: 138 case Instruction::FMul: 139 case Instruction::FDiv: 140 case Instruction::FRem: 141 return {Weight, {anyFloatOrVecFloatType(), matchFirstType()}, buildOp}; 142 case Instruction::BinaryOpsEnd: 143 llvm_unreachable("Value out of range of enum"); 144 } 145 llvm_unreachable("Covered switch"); 146 } 147 148 OpDescriptor llvm::fuzzerop::cmpOpDescriptor(unsigned Weight, 149 Instruction::OtherOps CmpOp, 150 CmpInst::Predicate Pred) { 151 auto buildOp = [CmpOp, Pred](ArrayRef<Value *> Srcs, 152 BasicBlock::iterator InsertPt) { 153 return CmpInst::Create(CmpOp, Pred, Srcs[0], Srcs[1], "C", InsertPt); 154 }; 155 156 switch (CmpOp) { 157 case Instruction::ICmp: 158 return {Weight, {anyIntOrVecIntType(), matchFirstType()}, buildOp}; 159 case Instruction::FCmp: 160 return {Weight, {anyFloatOrVecFloatType(), matchFirstType()}, buildOp}; 161 default: 162 llvm_unreachable("CmpOp must be ICmp or FCmp"); 163 } 164 } 165 166 OpDescriptor llvm::fuzzerop::splitBlockDescriptor(unsigned Weight) { 167 auto buildSplitBlock = [](ArrayRef<Value *> Srcs, 168 BasicBlock::iterator InsertPt) { 169 BasicBlock *Block = InsertPt->getParent(); 170 BasicBlock *Next = Block->splitBasicBlock(InsertPt, "BB"); 171 172 // If it was an exception handling block, we are done. 173 if (Block->isEHPad()) 174 return nullptr; 175 176 // Loop back on this block by replacing the unconditional forward branch 177 // with a conditional with a backedge. 178 if (Block != &Block->getParent()->getEntryBlock()) { 179 BranchInst::Create(Block, Next, Srcs[0], 180 Block->getTerminator()->getIterator()); 181 Block->getTerminator()->eraseFromParent(); 182 183 // We need values for each phi in the block. Since there isn't a good way 184 // to do a variable number of input values currently, we just fill them 185 // with poison. 186 for (PHINode &PHI : Block->phis()) 187 PHI.addIncoming(PoisonValue::get(PHI.getType()), Block); 188 } 189 return nullptr; 190 }; 191 SourcePred isInt1Ty{[](ArrayRef<Value *>, const Value *V) { 192 return V->getType()->isIntegerTy(1); 193 }, 194 std::nullopt}; 195 return {Weight, {isInt1Ty}, buildSplitBlock}; 196 } 197 198 OpDescriptor llvm::fuzzerop::gepDescriptor(unsigned Weight) { 199 auto buildGEP = [](ArrayRef<Value *> Srcs, BasicBlock::iterator InsertPt) { 200 // TODO: It would be better to generate a random type here, rather than 201 // generating a random value and picking its type. 202 Type *Ty = Srcs[1]->getType(); 203 auto Indices = ArrayRef(Srcs).drop_front(2); 204 return GetElementPtrInst::Create(Ty, Srcs[0], Indices, "G", InsertPt); 205 }; 206 // TODO: Handle aggregates and vectors 207 // TODO: Support multiple indices. 208 // TODO: Try to avoid meaningless accesses. 209 SourcePred sizedType( 210 [](ArrayRef<Value *>, const Value *V) { return V->getType()->isSized(); }, 211 std::nullopt); 212 return {Weight, {sizedPtrType(), sizedType, anyIntType()}, buildGEP}; 213 } 214 215 static uint64_t getAggregateNumElements(Type *T) { 216 assert(T->isAggregateType() && "Not a struct or array"); 217 if (isa<StructType>(T)) 218 return T->getStructNumElements(); 219 return T->getArrayNumElements(); 220 } 221 222 static SourcePred validExtractValueIndex() { 223 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 224 if (auto *CI = dyn_cast<ConstantInt>(V)) 225 if (!CI->uge(getAggregateNumElements(Cur[0]->getType()))) 226 return true; 227 return false; 228 }; 229 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 230 std::vector<Constant *> Result; 231 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 232 uint64_t N = getAggregateNumElements(Cur[0]->getType()); 233 // Create indices at the start, end, and middle, but avoid dups. 234 Result.push_back(ConstantInt::get(Int32Ty, 0)); 235 if (N > 1) 236 Result.push_back(ConstantInt::get(Int32Ty, N - 1)); 237 if (N > 2) 238 Result.push_back(ConstantInt::get(Int32Ty, N / 2)); 239 return Result; 240 }; 241 return {Pred, Make}; 242 } 243 244 OpDescriptor llvm::fuzzerop::extractValueDescriptor(unsigned Weight) { 245 auto buildExtract = [](ArrayRef<Value *> Srcs, 246 BasicBlock::iterator InsertPt) { 247 // TODO: It's pretty inefficient to shuffle this all through constants. 248 unsigned Idx = cast<ConstantInt>(Srcs[1])->getZExtValue(); 249 return ExtractValueInst::Create(Srcs[0], {Idx}, "E", InsertPt); 250 }; 251 // TODO: Should we handle multiple indices? 252 return {Weight, {anyAggregateType(), validExtractValueIndex()}, buildExtract}; 253 } 254 255 static SourcePred matchScalarInAggregate() { 256 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 257 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType())) 258 return V->getType() == ArrayT->getElementType(); 259 260 auto *STy = cast<StructType>(Cur[0]->getType()); 261 for (int I = 0, E = STy->getNumElements(); I < E; ++I) 262 if (STy->getTypeAtIndex(I) == V->getType()) 263 return true; 264 return false; 265 }; 266 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *>) { 267 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType())) 268 return makeConstantsWithType(ArrayT->getElementType()); 269 270 std::vector<Constant *> Result; 271 auto *STy = cast<StructType>(Cur[0]->getType()); 272 for (int I = 0, E = STy->getNumElements(); I < E; ++I) 273 makeConstantsWithType(STy->getTypeAtIndex(I), Result); 274 return Result; 275 }; 276 return {Pred, Make}; 277 } 278 279 static SourcePred validInsertValueIndex() { 280 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 281 if (auto *CI = dyn_cast<ConstantInt>(V)) 282 if (CI->getBitWidth() == 32) { 283 Type *Indexed = ExtractValueInst::getIndexedType(Cur[0]->getType(), 284 CI->getZExtValue()); 285 return Indexed == Cur[1]->getType(); 286 } 287 return false; 288 }; 289 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 290 std::vector<Constant *> Result; 291 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 292 auto *BaseTy = Cur[0]->getType(); 293 int I = 0; 294 while (Type *Indexed = ExtractValueInst::getIndexedType(BaseTy, I)) { 295 if (Indexed == Cur[1]->getType()) 296 Result.push_back(ConstantInt::get(Int32Ty, I)); 297 ++I; 298 } 299 return Result; 300 }; 301 return {Pred, Make}; 302 } 303 304 OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) { 305 auto buildInsert = [](ArrayRef<Value *> Srcs, BasicBlock::iterator InsertPt) { 306 // TODO: It's pretty inefficient to shuffle this all through constants. 307 unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue(); 308 return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", InsertPt); 309 }; 310 return { 311 Weight, 312 {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()}, 313 buildInsert}; 314 } 315 316 OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) { 317 auto buildExtract = [](ArrayRef<Value *> Srcs, 318 BasicBlock::iterator InsertPt) { 319 return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", InsertPt); 320 }; 321 // TODO: Try to avoid undefined accesses. 322 return {Weight, {anyVectorType(), anyIntType()}, buildExtract}; 323 } 324 325 OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) { 326 auto buildInsert = [](ArrayRef<Value *> Srcs, BasicBlock::iterator InsertPt) { 327 return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", InsertPt); 328 }; 329 // TODO: Try to avoid undefined accesses. 330 return {Weight, 331 {anyVectorType(), matchScalarOfFirstType(), anyIntType()}, 332 buildInsert}; 333 } 334 335 static SourcePred validShuffleVectorIndex() { 336 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 337 return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V); 338 }; 339 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 340 auto *FirstTy = cast<VectorType>(Cur[0]->getType()); 341 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 342 // TODO: It's straighforward to make up reasonable values, but listing them 343 // exhaustively would be insane. Come up with a couple of sensible ones. 344 return std::vector<Constant *>{ 345 PoisonValue::get(VectorType::get(Int32Ty, FirstTy->getElementCount()))}; 346 }; 347 return {Pred, Make}; 348 } 349 350 OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) { 351 auto buildShuffle = [](ArrayRef<Value *> Srcs, 352 BasicBlock::iterator InsertPt) { 353 return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", InsertPt); 354 }; 355 return {Weight, 356 {anyVectorType(), matchFirstType(), validShuffleVectorIndex()}, 357 buildShuffle}; 358 } 359