LLVM  15.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()
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 
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 
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 
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 }
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:264
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:17
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:136
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:382
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:167
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:1769
RandomIRBuilder.h
BasicBlock.h
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:305
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:98
llvm::RandomIRBuilder::newSink
void newSink(BasicBlock &BB, ArrayRef< Instruction * > Insts, Value *V)
Create a user for V in BB.
Definition: RandomIRBuilder.cpp:123
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: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:176
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:524
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
llvm::Type::isOpaquePointerTy
bool isOpaquePointerTy() const
True if this is an instance of an opaque PointerType.
Definition: Type.cpp:61
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:58
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:243
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43