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[1]->getType(); 200 auto Indices = ArrayRef(Srcs).drop_front(2); 201 return GetElementPtrInst::Create(Ty, Srcs[0], Indices, "G", Inst); 202 }; 203 // TODO: Handle aggregates and vectors 204 // TODO: Support multiple indices. 205 // TODO: Try to avoid meaningless accesses. 206 SourcePred sizedType( 207 [](ArrayRef<Value *>, const Value *V) { return V->getType()->isSized(); }, 208 std::nullopt); 209 return {Weight, {sizedPtrType(), sizedType, anyIntType()}, buildGEP}; 210 } 211 212 static uint64_t getAggregateNumElements(Type *T) { 213 assert(T->isAggregateType() && "Not a struct or array"); 214 if (isa<StructType>(T)) 215 return T->getStructNumElements(); 216 return T->getArrayNumElements(); 217 } 218 219 static SourcePred validExtractValueIndex() { 220 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 221 if (auto *CI = dyn_cast<ConstantInt>(V)) 222 if (!CI->uge(getAggregateNumElements(Cur[0]->getType()))) 223 return true; 224 return false; 225 }; 226 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 227 std::vector<Constant *> Result; 228 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 229 uint64_t N = getAggregateNumElements(Cur[0]->getType()); 230 // Create indices at the start, end, and middle, but avoid dups. 231 Result.push_back(ConstantInt::get(Int32Ty, 0)); 232 if (N > 1) 233 Result.push_back(ConstantInt::get(Int32Ty, N - 1)); 234 if (N > 2) 235 Result.push_back(ConstantInt::get(Int32Ty, N / 2)); 236 return Result; 237 }; 238 return {Pred, Make}; 239 } 240 241 OpDescriptor llvm::fuzzerop::extractValueDescriptor(unsigned Weight) { 242 auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 243 // TODO: It's pretty inefficient to shuffle this all through constants. 244 unsigned Idx = cast<ConstantInt>(Srcs[1])->getZExtValue(); 245 return ExtractValueInst::Create(Srcs[0], {Idx}, "E", Inst); 246 }; 247 // TODO: Should we handle multiple indices? 248 return {Weight, {anyAggregateType(), validExtractValueIndex()}, buildExtract}; 249 } 250 251 static SourcePred matchScalarInAggregate() { 252 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 253 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType())) 254 return V->getType() == ArrayT->getElementType(); 255 256 auto *STy = cast<StructType>(Cur[0]->getType()); 257 for (int I = 0, E = STy->getNumElements(); I < E; ++I) 258 if (STy->getTypeAtIndex(I) == V->getType()) 259 return true; 260 return false; 261 }; 262 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *>) { 263 if (auto *ArrayT = dyn_cast<ArrayType>(Cur[0]->getType())) 264 return makeConstantsWithType(ArrayT->getElementType()); 265 266 std::vector<Constant *> Result; 267 auto *STy = cast<StructType>(Cur[0]->getType()); 268 for (int I = 0, E = STy->getNumElements(); I < E; ++I) 269 makeConstantsWithType(STy->getTypeAtIndex(I), Result); 270 return Result; 271 }; 272 return {Pred, Make}; 273 } 274 275 static SourcePred validInsertValueIndex() { 276 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 277 if (auto *CI = dyn_cast<ConstantInt>(V)) 278 if (CI->getBitWidth() == 32) { 279 Type *Indexed = ExtractValueInst::getIndexedType(Cur[0]->getType(), 280 CI->getZExtValue()); 281 return Indexed == Cur[1]->getType(); 282 } 283 return false; 284 }; 285 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 286 std::vector<Constant *> Result; 287 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 288 auto *BaseTy = Cur[0]->getType(); 289 int I = 0; 290 while (Type *Indexed = ExtractValueInst::getIndexedType(BaseTy, I)) { 291 if (Indexed == Cur[1]->getType()) 292 Result.push_back(ConstantInt::get(Int32Ty, I)); 293 ++I; 294 } 295 return Result; 296 }; 297 return {Pred, Make}; 298 } 299 300 OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) { 301 auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 302 // TODO: It's pretty inefficient to shuffle this all through constants. 303 unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue(); 304 return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", Inst); 305 }; 306 return { 307 Weight, 308 {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()}, 309 buildInsert}; 310 } 311 312 OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) { 313 auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 314 return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", Inst); 315 }; 316 // TODO: Try to avoid undefined accesses. 317 return {Weight, {anyVectorType(), anyIntType()}, buildExtract}; 318 } 319 320 OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) { 321 auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 322 return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", Inst); 323 }; 324 // TODO: Try to avoid undefined accesses. 325 return {Weight, 326 {anyVectorType(), matchScalarOfFirstType(), anyIntType()}, 327 buildInsert}; 328 } 329 330 static SourcePred validShuffleVectorIndex() { 331 auto Pred = [](ArrayRef<Value *> Cur, const Value *V) { 332 return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V); 333 }; 334 auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) { 335 auto *FirstTy = cast<VectorType>(Cur[0]->getType()); 336 auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext()); 337 // TODO: It's straighforward to make up reasonable values, but listing them 338 // exhaustively would be insane. Come up with a couple of sensible ones. 339 return std::vector<Constant *>{ 340 UndefValue::get(VectorType::get(Int32Ty, FirstTy->getElementCount()))}; 341 }; 342 return {Pred, Make}; 343 } 344 345 OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) { 346 auto buildShuffle = [](ArrayRef<Value *> Srcs, Instruction *Inst) { 347 return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", Inst); 348 }; 349 return {Weight, 350 {anyVectorType(), matchFirstType(), validShuffleVectorIndex()}, 351 buildShuffle}; 352 } 353