LLVM  13.0.0git
RandomIRBuilder.cpp
Go to the documentation of this file.
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 
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 
23  return findOrCreateSource(BB, Insts, {}, anyType());
24 }
25 
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 
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 
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 
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 
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 }
llvm::RandomIRBuilder::findOrCreateSource
Value * findOrCreateSource(BasicBlock &BB, ArrayRef< Instruction * > Insts)
Find a "source" for some operation, which will be used in one of the operation's operands.
Definition: RandomIRBuilder.cpp:21
llvm
Definition: AllocatorList.h:23
IntrinsicInst.h
llvm::PointerType::get
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space.
Definition: Type.cpp:693
llvm::RandomIRBuilder::findPointer
Value * findPointer(BasicBlock &BB, ArrayRef< Instruction * > Insts, ArrayRef< Value * > Srcs, fuzzerop::SourcePred Pred)
Definition: RandomIRBuilder.cpp:133
llvm::Use::getOperandNo
unsigned getOperandNo() const
Return the operand # of this use in its User.
Definition: Use.cpp:33
STLExtras.h
llvm::fuzzerop::matchFirstType
static SourcePred matchFirstType()
Match values that have the same type as the first source.
Definition: OpDescriptor.h:194
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::ArrayRef::back
const T & back() const
back - Get the last element.
Definition: ArrayRef.h:172
Constants.h
llvm::fuzzerop::anyType
static SourcePred anyType()
Definition: OpDescriptor.h:105
llvm::User
Definition: User.h:44
IP
Definition: NVPTXLowerArgs.cpp:166
llvm::Instruction
Definition: Instruction.h:45
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
RandomIRBuilder.h
BasicBlock.h
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::uniform
T uniform(GenT &Gen, T Min, T Max)
Return a uniformly distributed random value between Min and Max.
Definition: Random.h:21
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::RandomIRBuilder::connectToSink
void connectToSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Find a viable user for V in Insts, which should all be contained in BB.
Definition: RandomIRBuilder.cpp:95
llvm::RandomIRBuilder::newSink
void newSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Create a user for V in BB.
Definition: RandomIRBuilder.cpp:120
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::cl::Sink
@ Sink
Definition: CommandLine.h:168
llvm::fuzzerop::SourcePred::matches
bool matches(ArrayRef< Value * > Cur, const Value *New)
Returns true if New is compatible for the argument after Cur.
Definition: OpDescriptor.h:77
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::make_filter_range
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:495
llvm::makeSampler
ReservoirSampler< ElT, GenT > makeSampler(GenT &RandGen, RangeT &&Items)
Definition: Random.h:75
Random.h
llvm::fuzzerop::SourcePred
A matcher/generator for finding suitable values for the next source in an operation's partially compl...
Definition: OpDescriptor.h:43
Function.h
llvm::RandomIRBuilder::newSource
Value * newSource(BasicBlock &BB, ArrayRef< Instruction * > Insts, ArrayRef< Value * > Srcs, fuzzerop::SourcePred Pred)
Create some Value suitable as a source for some operation.
Definition: RandomIRBuilder.cpp:41
Instructions.h
llvm::fuzzerop::SourcePred::generate
std::vector< Constant * > generate(ArrayRef< Value * > Cur, ArrayRef< Type * > BaseTypes)
Generates a list of potential values for the argument after Cur.
Definition: OpDescriptor.h:82
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
isCompatibleReplacement
static bool isCompatibleReplacement(const Instruction *I, const Use &Operand, const Value *Replacement)
Definition: RandomIRBuilder.cpp:70
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44