1 //===-- RandomIRBuilder.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/RandomIRBuilder.h" 10 #include "llvm/ADT/STLExtras.h" 11 #include "llvm/FuzzMutate/OpDescriptor.h" 12 #include "llvm/FuzzMutate/Random.h" 13 #include "llvm/IR/BasicBlock.h" 14 #include "llvm/IR/Constants.h" 15 #include "llvm/IR/DataLayout.h" 16 #include "llvm/IR/Instructions.h" 17 #include "llvm/IR/IntrinsicInst.h" 18 19 using namespace llvm; 20 using namespace fuzzerop; 21 22 Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB, 23 ArrayRef<Instruction *> Insts) { 24 return findOrCreateSource(BB, Insts, {}, anyType()); 25 } 26 27 Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB, 28 ArrayRef<Instruction *> Insts, 29 ArrayRef<Value *> Srcs, 30 SourcePred Pred, 31 bool allowConstant) { 32 auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) { 33 return Pred.matches(Srcs, Inst); 34 }; 35 auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred)); 36 // Also consider choosing no source, meaning we want a new one. 37 RS.sample(nullptr, /*Weight=*/1); 38 if (Instruction *Src = RS.getSelection()) 39 return Src; 40 return newSource(BB, Insts, Srcs, Pred, allowConstant); 41 } 42 43 Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts, 44 ArrayRef<Value *> Srcs, SourcePred Pred, 45 bool allowConstant) { 46 // Generate some constants to choose from. 47 auto RS = makeSampler<Value *>(Rand); 48 RS.sample(Pred.generate(Srcs, KnownTypes)); 49 50 // If we can find a pointer to load from, use it half the time. 51 Value *Ptr = findPointer(BB, Insts, Srcs, Pred); 52 if (Ptr) { 53 // Create load from the chosen pointer 54 auto IP = BB.getFirstInsertionPt(); 55 if (auto *I = dyn_cast<Instruction>(Ptr)) { 56 IP = ++I->getIterator(); 57 assert(IP != BB.end() && "guaranteed by the findPointer"); 58 } 59 // For opaque pointers, pick the type independently. 60 Type *AccessTy = Ptr->getType()->isOpaquePointerTy() 61 ? RS.getSelection()->getType() 62 : Ptr->getType()->getNonOpaquePointerElementType(); 63 auto *NewLoad = new LoadInst(AccessTy, Ptr, "L", &*IP); 64 65 // Only sample this load if it really matches the descriptor 66 if (Pred.matches(Srcs, NewLoad)) 67 RS.sample(NewLoad, RS.totalWeight()); 68 else 69 NewLoad->eraseFromParent(); 70 } 71 72 Value *newSrc = RS.getSelection(); 73 // Generate a stack alloca and store the constant to it if constant is not 74 // allowed, our hope is that later mutations can generate some values and 75 // store to this placeholder. 76 if (!allowConstant && isa<Constant>(newSrc)) { 77 Type *Ty = newSrc->getType(); 78 Function *F = BB.getParent(); 79 BasicBlock *EntryBB = &F->getEntryBlock(); 80 /// TODO: For all Allocas, maybe allocate an array. 81 DataLayout DL(BB.getParent()->getParent()); 82 AllocaInst *Alloca = new AllocaInst(Ty, DL.getProgramAddressSpace(), "A", 83 EntryBB->getTerminator()); 84 new StoreInst(newSrc, Alloca, EntryBB->getTerminator()); 85 if (BB.getTerminator()) { 86 newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", BB.getTerminator()); 87 } else { 88 newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", &BB); 89 } 90 } 91 return newSrc; 92 } 93 94 static bool isCompatibleReplacement(const Instruction *I, const Use &Operand, 95 const Value *Replacement) { 96 unsigned int OperandNo = Operand.getOperandNo(); 97 if (Operand->getType() != Replacement->getType()) 98 return false; 99 switch (I->getOpcode()) { 100 case Instruction::GetElementPtr: 101 case Instruction::ExtractElement: 102 case Instruction::ExtractValue: 103 // TODO: We could potentially validate these, but for now just leave indices 104 // alone. 105 if (OperandNo >= 1) 106 return false; 107 break; 108 case Instruction::InsertValue: 109 case Instruction::InsertElement: 110 case Instruction::ShuffleVector: 111 if (OperandNo >= 2) 112 return false; 113 break; 114 // For Br/Switch, we only try to modify the 1st Operand (condition). 115 // Modify other operands, like switch case may accidently change case from 116 // ConstantInt to a register, which is illegal. 117 case Instruction::Switch: 118 case Instruction::Br: 119 if (OperandNo >= 1) 120 return false; 121 break; 122 default: 123 break; 124 } 125 return true; 126 } 127 128 void RandomIRBuilder::connectToSink(BasicBlock &BB, 129 ArrayRef<Instruction *> Insts, Value *V) { 130 auto RS = makeSampler<Use *>(Rand); 131 for (auto &I : Insts) { 132 if (isa<IntrinsicInst>(I)) 133 // TODO: Replacing operands of intrinsics would be interesting, but 134 // there's no easy way to verify that a given replacement is valid given 135 // that intrinsics can impose arbitrary constraints. 136 continue; 137 for (Use &U : I->operands()) 138 if (isCompatibleReplacement(I, U, V)) 139 RS.sample(&U, 1); 140 } 141 // Also consider choosing no sink, meaning we want a new one. 142 RS.sample(nullptr, /*Weight=*/1); 143 144 if (Use *Sink = RS.getSelection()) { 145 User *U = Sink->getUser(); 146 unsigned OpNo = Sink->getOperandNo(); 147 U->setOperand(OpNo, V); 148 return; 149 } 150 newSink(BB, Insts, V); 151 } 152 153 void RandomIRBuilder::newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, 154 Value *V) { 155 Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType()); 156 if (!Ptr) { 157 if (uniform(Rand, 0, 1)) 158 Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt()); 159 else 160 Ptr = UndefValue::get(PointerType::get(V->getType(), 0)); 161 } 162 163 new StoreInst(V, Ptr, Insts.back()); 164 } 165 166 Value *RandomIRBuilder::findPointer(BasicBlock &BB, 167 ArrayRef<Instruction *> Insts, 168 ArrayRef<Value *> Srcs, SourcePred Pred) { 169 auto IsMatchingPtr = [&Srcs, &Pred](Instruction *Inst) { 170 // Invoke instructions sometimes produce valid pointers but currently 171 // we can't insert loads or stores from them 172 if (Inst->isTerminator()) 173 return false; 174 175 if (auto *PtrTy = dyn_cast<PointerType>(Inst->getType())) { 176 if (PtrTy->isOpaque()) 177 return true; 178 179 // We can never generate loads from non first class or non sized types 180 Type *ElemTy = PtrTy->getNonOpaquePointerElementType(); 181 if (!ElemTy->isSized() || !ElemTy->isFirstClassType()) 182 return false; 183 184 // TODO: Check if this is horribly expensive. 185 return Pred.matches(Srcs, UndefValue::get(ElemTy)); 186 } 187 return false; 188 }; 189 if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr))) 190 return RS.getSelection(); 191 return nullptr; 192 } 193 194 Type *RandomIRBuilder::randomType() { 195 uint64_t TyIdx = uniform<uint64_t>(Rand, 0, KnownTypes.size() - 1); 196 return KnownTypes[TyIdx]; 197 } 198