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/Random.h" 12 #include "llvm/IR/BasicBlock.h" 13 #include "llvm/IR/Constants.h" 14 #include "llvm/IR/Function.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 auto *NewLoad = new LoadInst( 57 cast<PointerType>(Ptr->getType())->getElementType(), 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 (Inst->isTerminator()) 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