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