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, Instruction *Inst) { 102 return SelectInst::Create(Srcs[0], Srcs[1], Srcs[2], "S", Inst); 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, Instruction *Inst) { 111 return UnaryOperator::Create(Instruction::FNeg, Srcs[0], "F", Inst); 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, Instruction *Inst) { 119 return BinaryOperator::Create(Op, Srcs[0], Srcs[1], "B", Inst); 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, Instruction *Inst) { 152 return CmpInst::Create(CmpOp, Pred, Srcs[0], Srcs[1], "C", Inst); 153 }; 154 155 switch (CmpOp) { 156 case Instruction::ICmp: 157 return {Weight, {anyIntOrVecIntType(), matchFirstType()}, buildOp}; 158 case Instruction::FCmp: 159 return {Weight, {anyFloatOrVecFloatType(), matchFirstType()}, buildOp}; 160 default: 161 llvm_unreachable("CmpOp must be ICmp or FCmp"); 162 } 163 } 164 165 OpDescriptor llvm::fuzzerop::splitBlockDescriptor(unsigned Weight) { 166 auto buildSplitBlock = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 167 BasicBlock *Block = Inst->getParent(); 168 BasicBlock *Next = Block->splitBasicBlock(Inst, "BB"); 169 170 // If it was an exception handling block, we are done. 171 if (Block->isEHPad()) 172 return nullptr; 173 174 // Loop back on this block by replacing the unconditional forward branch 175 // with a conditional with a backedge. 176 if (Block != &Block->getParent()->getEntryBlock()) { 177 BranchInst::Create(Block, Next, Srcs[0], Block->getTerminator()); 178 Block->getTerminator()->eraseFromParent(); 179 180 // We need values for each phi in the block. Since there isn't a good way 181 // to do a variable number of input values currently, we just fill them 182 // with undef. 183 for (PHINode &PHI : Block->phis()) 184 PHI.addIncoming(UndefValue::get(PHI.getType()), Block); 185 } 186 return nullptr; 187 }; 188 SourcePred isInt1Ty{[](ArrayRef<Value *>, const Value *V) { 189 return V->getType()->isIntegerTy(1); 190 }, 191 std::nullopt}; 192 return {Weight, {isInt1Ty}, buildSplitBlock}; 193 } 194 195 OpDescriptor llvm::fuzzerop::gepDescriptor(unsigned Weight) { 196 auto buildGEP = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 197 // TODO: It would be better to generate a random type here, rather than 198 // generating a random value and picking its type. 199 Type *Ty = Srcs[0]->getType()->isOpaquePointerTy() 200 ? Srcs[1]->getType() 201 : Srcs[0]->getType()->getNonOpaquePointerElementType(); 202 auto Indices = ArrayRef(Srcs).drop_front(2); 203 return GetElementPtrInst::Create(Ty, Srcs[0], Indices, "G", Inst); 204 }; 205 // TODO: Handle aggregates and vectors 206 // TODO: Support multiple indices. 207 // TODO: Try to avoid meaningless accesses. 208 SourcePred sizedType( 209 [](ArrayRef<Value *>, const Value *V) { return V->getType()->isSized(); }, 210 std::nullopt); 211 return {Weight, {sizedPtrType(), sizedType, anyIntType()}, buildGEP}; 212 } 213 214 static uint64_t getAggregateNumElements(Type *T) { 215 assert(T->isAggregateType() && "Not a struct or array"); 216 if (isa<StructType>(T)) 217 return T->getStructNumElements(); 218 return T->getArrayNumElements(); 219 } 220 221 static SourcePred validExtractValueIndex() { 222 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 223 if (auto *CI = dyn_cast<ConstantInt>(V)) 224 if (!CI->uge(getAggregateNumElements(Cur[0]->getType()))) 225 return true; 226 return false; 227 }; 228 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 229 std::vector<Constant *> Result; 230 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 231 uint64_t N = getAggregateNumElements(Cur[0]->getType()); 232 // Create indices at the start, end, and middle, but avoid dups. 233 Result.push_back(ConstantInt::get(Int32Ty, 0)); 234 if (N > 1) 235 Result.push_back(ConstantInt::get(Int32Ty, N - 1)); 236 if (N > 2) 237 Result.push_back(ConstantInt::get(Int32Ty, N / 2)); 238 return Result; 239 }; 240 return {Pred, Make}; 241 } 242 243 OpDescriptor llvm::fuzzerop::extractValueDescriptor(unsigned Weight) { 244 auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 245 // TODO: It's pretty inefficient to shuffle this all through constants. 246 unsigned Idx = cast<ConstantInt>(Srcs[1])->getZExtValue(); 247 return ExtractValueInst::Create(Srcs[0], {Idx}, "E", Inst); 248 }; 249 // TODO: Should we handle multiple indices? 250 return {Weight, {anyAggregateType(), validExtractValueIndex()}, buildExtract}; 251 } 252 253 static SourcePred matchScalarInAggregate() { 254 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 255 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType())) 256 return V->getType() == ArrayT->getElementType(); 257 258 auto *STy = cast<StructType>(Cur[0]->getType()); 259 for (int I = 0, E = STy->getNumElements(); I < E; ++I) 260 if (STy->getTypeAtIndex(I) == V->getType()) 261 return true; 262 return false; 263 }; 264 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *>) { 265 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType())) 266 return makeConstantsWithType(ArrayT->getElementType()); 267 268 std::vector<Constant *> Result; 269 auto *STy = cast<StructType>(Cur[0]->getType()); 270 for (int I = 0, E = STy->getNumElements(); I < E; ++I) 271 makeConstantsWithType(STy->getTypeAtIndex(I), Result); 272 return Result; 273 }; 274 return {Pred, Make}; 275 } 276 277 static SourcePred validInsertValueIndex() { 278 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 279 if (auto *CI = dyn_cast<ConstantInt>(V)) 280 if (CI->getBitWidth() == 32) { 281 Type *Indexed = ExtractValueInst::getIndexedType(Cur[0]->getType(), 282 CI->getZExtValue()); 283 return Indexed == Cur[1]->getType(); 284 } 285 return false; 286 }; 287 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 288 std::vector<Constant *> Result; 289 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 290 auto *BaseTy = Cur[0]->getType(); 291 int I = 0; 292 while (Type *Indexed = ExtractValueInst::getIndexedType(BaseTy, I)) { 293 if (Indexed == Cur[1]->getType()) 294 Result.push_back(ConstantInt::get(Int32Ty, I)); 295 ++I; 296 } 297 return Result; 298 }; 299 return {Pred, Make}; 300 } 301 302 OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) { 303 auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 304 // TODO: It's pretty inefficient to shuffle this all through constants. 305 unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue(); 306 return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", Inst); 307 }; 308 return { 309 Weight, 310 {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()}, 311 buildInsert}; 312 } 313 314 OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) { 315 auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 316 return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", Inst); 317 }; 318 // TODO: Try to avoid undefined accesses. 319 return {Weight, {anyVectorType(), anyIntType()}, buildExtract}; 320 } 321 322 OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) { 323 auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 324 return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", Inst); 325 }; 326 // TODO: Try to avoid undefined accesses. 327 return {Weight, 328 {anyVectorType(), matchScalarOfFirstType(), anyIntType()}, 329 buildInsert}; 330 } 331 332 static SourcePred validShuffleVectorIndex() { 333 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 334 return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V); 335 }; 336 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 337 auto *FirstTy = cast<VectorType>(Cur[0]->getType()); 338 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 339 // TODO: It's straighforward to make up reasonable values, but listing them 340 // exhaustively would be insane. Come up with a couple of sensible ones. 341 return std::vector<Constant *>{ 342 UndefValue::get(VectorType::get(Int32Ty, FirstTy->getElementCount()))}; 343 }; 344 return {Pred, Make}; 345 } 346 347 OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) { 348 auto buildShuffle = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 349 return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", Inst); 350 }; 351 return {Weight, 352 {anyVectorType(), matchFirstType(), validShuffleVectorIndex()}, 353 buildShuffle}; 354 } 355