LLVM  16.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"
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 
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  // 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  unsigned int OperandNo = Operand.getOperandNo();
76  if (Operand->getType() != Replacement->getType())
77  return false;
78  switch (I->getOpcode()) {
79  case Instruction::GetElementPtr:
80  case Instruction::ExtractElement:
81  case Instruction::ExtractValue:
82  // TODO: We could potentially validate these, but for now just leave indices
83  // alone.
84  if (OperandNo >= 1)
85  return false;
86  break;
87  case Instruction::InsertValue:
88  case Instruction::InsertElement:
89  case Instruction::ShuffleVector:
90  if (OperandNo >= 2)
91  return false;
92  break;
93  // For Br/Switch, we only try to modify the 1st Operand (condition).
94  // Modify other operands, like switch case may accidently change case from
95  // ConstantInt to a register, which is illegal.
96  case Instruction::Switch:
97  case Instruction::Br:
98  if (OperandNo >= 1)
99  return false;
100  break;
101  default:
102  break;
103  }
104  return true;
105 }
106 
108  ArrayRef<Instruction *> Insts, Value *V) {
109  auto RS = makeSampler<Use *>(Rand);
110  for (auto &I : Insts) {
111  if (isa<IntrinsicInst>(I))
112  // TODO: Replacing operands of intrinsics would be interesting, but
113  // there's no easy way to verify that a given replacement is valid given
114  // that intrinsics can impose arbitrary constraints.
115  continue;
116  for (Use &U : I->operands())
117  if (isCompatibleReplacement(I, U, V))
118  RS.sample(&U, 1);
119  }
120  // Also consider choosing no sink, meaning we want a new one.
121  RS.sample(nullptr, /*Weight=*/1);
122 
123  if (Use *Sink = RS.getSelection()) {
124  User *U = Sink->getUser();
125  unsigned OpNo = Sink->getOperandNo();
126  U->setOperand(OpNo, V);
127  return;
128  }
129  newSink(BB, Insts, V);
130 }
131 
133  Value *V) {
134  Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType());
135  if (!Ptr) {
136  if (uniform(Rand, 0, 1))
137  Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt());
138  else
140  }
141 
142  new StoreInst(V, Ptr, Insts.back());
143 }
144 
147  ArrayRef<Value *> Srcs, SourcePred Pred) {
148  auto IsMatchingPtr = [&Srcs, &Pred](Instruction *Inst) {
149  // Invoke instructions sometimes produce valid pointers but currently
150  // we can't insert loads or stores from them
151  if (Inst->isTerminator())
152  return false;
153 
154  if (auto *PtrTy = dyn_cast<PointerType>(Inst->getType())) {
155  if (PtrTy->isOpaque())
156  return true;
157 
158  // We can never generate loads from non first class or non sized types
159  Type *ElemTy = PtrTy->getNonOpaquePointerElementType();
160  if (!ElemTy->isSized() || !ElemTy->isFirstClassType())
161  return false;
162 
163  // TODO: Check if this is horribly expensive.
164  return Pred.matches(Srcs, UndefValue::get(ElemTy));
165  }
166  return false;
167  };
168  if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
169  return RS.getSelection();
170  return nullptr;
171 }
172 
174  uint64_t TyIdx = uniform<uint64_t>(Rand, 0, KnownTypes.size() - 1);
175  return KnownTypes[TyIdx];
176 }
OpDescriptor.h
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:283
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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:727
llvm::RandomIRBuilder::findPointer
Value * findPointer(BasicBlock &BB, ArrayRef< Instruction * > Insts, ArrayRef< Value * > Srcs, fuzzerop::SourcePred Pred)
Definition: RandomIRBuilder.cpp:145
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::Use::getOperandNo
unsigned getOperandNo() const
Return the operand # of this use in its User.
Definition: Use.cpp:31
STLExtras.h
llvm::Type::getNonOpaquePointerElementType
Type * getNonOpaquePointerElementType() const
Only use this method in code that is not reachable with opaque pointers, or part of deprecated method...
Definition: Type.h:401
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:55
llvm::ArrayRef::back
const T & back() const
back - Get the last element.
Definition: ArrayRef.h:173
Constants.h
llvm::fuzzerop::anyType
static SourcePred anyType()
Definition: OpDescriptor.h:104
llvm::User
Definition: User.h:44
IP
Definition: NVPTXLowerArgs.cpp:168
llvm::Instruction
Definition: Instruction.h:42
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1713
RandomIRBuilder.h
BasicBlock.h
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:298
llvm::RandomIRBuilder::randomType
Type * randomType()
Return a uniformly choosen type from AllowedTypes.
Definition: RandomIRBuilder.cpp:173
uint64_t
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:58
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:107
llvm::RandomIRBuilder::newSink
void newSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Create a user for V in BB.
Definition: RandomIRBuilder.cpp:132
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Ptr
@ Ptr
Definition: TargetLibraryInfo.cpp:60
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:32
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::cl::Sink
@ Sink
Definition: CommandLine.h:167
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:76
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:632
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:42
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:81
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:59
isCompatibleReplacement
static bool isCompatibleReplacement(const Instruction *I, const Use &Operand, const Value *Replacement)
Definition: RandomIRBuilder.cpp:73
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::Type::isFirstClassType
bool isFirstClassType() const
Return true if the type is "first class", meaning it is a valid type for a Value.
Definition: Type.h:262
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43