1 //===-- RandomIRBuilder.cpp -----------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/FuzzMutate/RandomIRBuilder.h" 11 #include "llvm/ADT/STLExtras.h" 12 #include "llvm/FuzzMutate/Random.h" 13 #include "llvm/IR/BasicBlock.h" 14 #include "llvm/IR/Constants.h" 15 #include "llvm/IR/Function.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 auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) { 32 return Pred.matches(Srcs, Inst); 33 }; 34 auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred)); 35 // Also consider choosing no source, meaning we want a new one. 36 RS.sample(nullptr, /*Weight=*/1); 37 if (Instruction *Src = RS.getSelection()) 38 return Src; 39 return newSource(BB, Insts, Srcs, Pred); 40 } 41 42 Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts, 43 ArrayRef<Value *> Srcs, SourcePred Pred) { 44 // Generate some constants to choose from. 45 auto RS = makeSampler<Value *>(Rand); 46 RS.sample(Pred.generate(Srcs, KnownTypes)); 47 48 // If we can find a pointer to load from, use it half the time. 49 Value *Ptr = findPointer(BB, Insts, Srcs, Pred); 50 if (Ptr) { 51 // Create load from the chosen pointer 52 auto IP = BB.getFirstInsertionPt(); 53 if (auto *I = dyn_cast<Instruction>(Ptr)) { 54 IP = ++I->getIterator(); 55 assert(IP != BB.end() && "guaranteed by the findPointer"); 56 } 57 auto *NewLoad = new LoadInst(Ptr, "L", &*IP); 58 59 // Only sample this load if it really matches the descriptor 60 if (Pred.matches(Srcs, NewLoad)) 61 RS.sample(NewLoad, RS.totalWeight()); 62 else 63 NewLoad->eraseFromParent(); 64 } 65 66 assert(!RS.isEmpty() && "Failed to generate sources"); 67 return RS.getSelection(); 68 } 69 70 static bool isCompatibleReplacement(const Instruction *I, const Use &Operand, 71 const Value *Replacement) { 72 if (Operand->getType() != Replacement->getType()) 73 return false; 74 switch (I->getOpcode()) { 75 case Instruction::GetElementPtr: 76 case Instruction::ExtractElement: 77 case Instruction::ExtractValue: 78 // TODO: We could potentially validate these, but for now just leave indices 79 // alone. 80 if (Operand.getOperandNo() >= 1) 81 return false; 82 break; 83 case Instruction::InsertValue: 84 case Instruction::InsertElement: 85 case Instruction::ShuffleVector: 86 if (Operand.getOperandNo() >= 2) 87 return false; 88 break; 89 default: 90 break; 91 } 92 return true; 93 } 94 95 void RandomIRBuilder::connectToSink(BasicBlock &BB, 96 ArrayRef<Instruction *> Insts, Value *V) { 97 auto RS = makeSampler<Use *>(Rand); 98 for (auto &I : Insts) { 99 if (isa<IntrinsicInst>(I)) 100 // TODO: Replacing operands of intrinsics would be interesting, but 101 // there's no easy way to verify that a given replacement is valid given 102 // that intrinsics can impose arbitrary constraints. 103 continue; 104 for (Use &U : I->operands()) 105 if (isCompatibleReplacement(I, U, V)) 106 RS.sample(&U, 1); 107 } 108 // Also consider choosing no sink, meaning we want a new one. 109 RS.sample(nullptr, /*Weight=*/1); 110 111 if (Use *Sink = RS.getSelection()) { 112 User *U = Sink->getUser(); 113 unsigned OpNo = Sink->getOperandNo(); 114 U->setOperand(OpNo, V); 115 return; 116 } 117 newSink(BB, Insts, V); 118 } 119 120 void RandomIRBuilder::newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, 121 Value *V) { 122 Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType()); 123 if (!Ptr) { 124 if (uniform(Rand, 0, 1)) 125 Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt()); 126 else 127 Ptr = UndefValue::get(PointerType::get(V->getType(), 0)); 128 } 129 130 new StoreInst(V, Ptr, Insts.back()); 131 } 132 133 Value *RandomIRBuilder::findPointer(BasicBlock &BB, 134 ArrayRef<Instruction *> Insts, 135 ArrayRef<Value *> Srcs, SourcePred Pred) { 136 auto IsMatchingPtr = [&Srcs, &Pred](Instruction *Inst) { 137 // Invoke instructions sometimes produce valid pointers but currently 138 // we can't insert loads or stores from them 139 if (isa<TerminatorInst>(Inst)) 140 return false; 141 142 if (auto PtrTy = dyn_cast<PointerType>(Inst->getType())) { 143 // We can never generate loads from non first class or non sized types 144 if (!PtrTy->getElementType()->isSized() || 145 !PtrTy->getElementType()->isFirstClassType()) 146 return false; 147 148 // TODO: Check if this is horribly expensive. 149 return Pred.matches(Srcs, UndefValue::get(PtrTy->getElementType())); 150 } 151 return false; 152 }; 153 if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr))) 154 return RS.getSelection(); 155 return nullptr; 156 } 157