1 //===-- IRMutator.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/IRMutator.h" 10 #include "llvm/ADT/Optional.h" 11 #include "llvm/Analysis/TargetLibraryInfo.h" 12 #include "llvm/FuzzMutate/Operations.h" 13 #include "llvm/FuzzMutate/Random.h" 14 #include "llvm/FuzzMutate/RandomIRBuilder.h" 15 #include "llvm/IR/BasicBlock.h" 16 #include "llvm/IR/Function.h" 17 #include "llvm/IR/InstIterator.h" 18 #include "llvm/IR/Instructions.h" 19 #include "llvm/IR/Module.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Transforms/Scalar/DCE.h" 22 23 using namespace llvm; 24 25 static void createEmptyFunction(Module &M) { 26 // TODO: Some arguments and a return value would probably be more interesting. 27 LLVMContext &Context = M.getContext(); 28 Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {}, 29 /*isVarArg=*/false), 30 GlobalValue::ExternalLinkage, "f", &M); 31 BasicBlock *BB = BasicBlock::Create(Context, "BB", F); 32 ReturnInst::Create(Context, BB); 33 } 34 35 void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) { 36 if (M.empty()) 37 createEmptyFunction(M); 38 39 auto RS = makeSampler<Function *>(IB.Rand); 40 for (Function &F : M) 41 if (!F.isDeclaration()) 42 RS.sample(&F, /*Weight=*/1); 43 mutate(*RS.getSelection(), IB); 44 } 45 46 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) { 47 mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB); 48 } 49 50 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) { 51 mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB); 52 } 53 54 void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize, 55 size_t MaxSize) { 56 std::vector<Type *> Types; 57 for (const auto &Getter : AllowedTypes) 58 Types.push_back(Getter(M.getContext())); 59 RandomIRBuilder IB(Seed, Types); 60 61 auto RS = makeSampler<IRMutationStrategy *>(IB.Rand); 62 for (const auto &Strategy : Strategies) 63 RS.sample(Strategy.get(), 64 Strategy->getWeight(CurSize, MaxSize, RS.totalWeight())); 65 auto Strategy = RS.getSelection(); 66 67 Strategy->mutate(M, IB); 68 } 69 70 static void eliminateDeadCode(Function &F) { 71 FunctionPassManager FPM; 72 FPM.addPass(DCEPass()); 73 FunctionAnalysisManager FAM; 74 FAM.registerPass([&] { return TargetLibraryAnalysis(); }); 75 FAM.registerPass([&] { return PassInstrumentationAnalysis(); }); 76 FPM.run(F, FAM); 77 } 78 79 void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) { 80 IRMutationStrategy::mutate(F, IB); 81 eliminateDeadCode(F); 82 } 83 84 std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() { 85 std::vector<fuzzerop::OpDescriptor> Ops; 86 describeFuzzerIntOps(Ops); 87 describeFuzzerFloatOps(Ops); 88 describeFuzzerControlFlowOps(Ops); 89 describeFuzzerPointerOps(Ops); 90 describeFuzzerAggregateOps(Ops); 91 describeFuzzerVectorOps(Ops); 92 return Ops; 93 } 94 95 Optional<fuzzerop::OpDescriptor> 96 InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) { 97 auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) { 98 return Op.SourcePreds[0].matches({}, Src); 99 }; 100 auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred)); 101 if (RS.isEmpty()) 102 return None; 103 return *RS; 104 } 105 106 void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) { 107 SmallVector<Instruction *, 32> Insts; 108 for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I) 109 Insts.push_back(&*I); 110 if (Insts.size() < 1) 111 return; 112 113 // Choose an insertion point for our new instruction. 114 size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1); 115 116 auto InstsBefore = makeArrayRef(Insts).slice(0, IP); 117 auto InstsAfter = makeArrayRef(Insts).slice(IP); 118 119 // Choose a source, which will be used to constrain the operation selection. 120 SmallVector<Value *, 2> Srcs; 121 Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore)); 122 123 // Choose an operation that's constrained to be valid for the type of the 124 // source, collect any other sources it needs, and then build it. 125 auto OpDesc = chooseOperation(Srcs[0], IB); 126 // Bail if no operation was found 127 if (!OpDesc) 128 return; 129 130 for (const auto &Pred : makeArrayRef(OpDesc->SourcePreds).slice(1)) 131 Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred)); 132 133 if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) { 134 // Find a sink and wire up the results of the operation. 135 IB.connectToSink(BB, InstsAfter, Op); 136 } 137 } 138 139 uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize, 140 uint64_t CurrentWeight) { 141 // If we have less than 200 bytes, panic and try to always delete. 142 if (CurrentSize > MaxSize - 200) 143 return CurrentWeight ? CurrentWeight * 100 : 1; 144 // Draw a line starting from when we only have 1k left and increasing linearly 145 // to double the current weight. 146 int64_t Line = (-2 * static_cast<int64_t>(CurrentWeight)) * 147 (static_cast<int64_t>(MaxSize) - 148 static_cast<int64_t>(CurrentSize) - 1000) / 149 1000; 150 // Clamp negative weights to zero. 151 if (Line < 0) 152 return 0; 153 return Line; 154 } 155 156 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) { 157 auto RS = makeSampler<Instruction *>(IB.Rand); 158 for (Instruction &Inst : instructions(F)) { 159 // TODO: We can't handle these instructions. 160 if (Inst.isTerminator() || Inst.isEHPad() || 161 Inst.isSwiftError() || isa<PHINode>(Inst)) 162 continue; 163 164 RS.sample(&Inst, /*Weight=*/1); 165 } 166 if (RS.isEmpty()) 167 return; 168 169 // Delete the instruction. 170 mutate(*RS.getSelection(), IB); 171 // Clean up any dead code that's left over after removing the instruction. 172 eliminateDeadCode(F); 173 } 174 175 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) { 176 assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG"); 177 178 if (Inst.getType()->isVoidTy()) { 179 // Instructions with void type (ie, store) have no uses to worry about. Just 180 // erase it and move on. 181 Inst.eraseFromParent(); 182 return; 183 } 184 185 // Otherwise we need to find some other value with the right type to keep the 186 // users happy. 187 auto Pred = fuzzerop::onlyType(Inst.getType()); 188 auto RS = makeSampler<Value *>(IB.Rand); 189 SmallVector<Instruction *, 32> InstsBefore; 190 BasicBlock *BB = Inst.getParent(); 191 for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E; 192 ++I) { 193 if (Pred.matches({}, &*I)) 194 RS.sample(&*I, /*Weight=*/1); 195 InstsBefore.push_back(&*I); 196 } 197 if (!RS) 198 RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1); 199 200 Inst.replaceAllUsesWith(RS.getSelection()); 201 Inst.eraseFromParent(); 202 } 203 204 void InstModificationIRStrategy::mutate(Instruction &Inst, 205 RandomIRBuilder &IB) { 206 SmallVector<std::function<void()>, 8> Modifications; 207 CmpInst *CI = nullptr; 208 GetElementPtrInst *GEP = nullptr; 209 switch (Inst.getOpcode()) { 210 default: 211 break; 212 case Instruction::Add: 213 case Instruction::Mul: 214 case Instruction::Sub: 215 case Instruction::Shl: 216 Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(true); }), 217 Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(false); }); 218 Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(true); }); 219 Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(false); }); 220 221 break; 222 case Instruction::ICmp: 223 CI = cast<ICmpInst>(&Inst); 224 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_EQ); }); 225 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_NE); }); 226 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGT); }); 227 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGE); }); 228 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULT); }); 229 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULE); }); 230 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGT); }); 231 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGE); }); 232 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLT); }); 233 Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLE); }); 234 break; 235 case Instruction::GetElementPtr: 236 GEP = cast<GetElementPtrInst>(&Inst); 237 Modifications.push_back([GEP]() { GEP->setIsInBounds(true); }); 238 Modifications.push_back([GEP]() { GEP->setIsInBounds(false); }); 239 break; 240 } 241 242 auto RS = makeSampler(IB.Rand, Modifications); 243 if (RS) 244 RS.getSelection()(); 245 } 246