Line data Source code
1 : //===-- RandomIRBuilder.cpp -----------------------------------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #include "llvm/FuzzMutate/RandomIRBuilder.h"
11 : #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/Function.h"
16 : #include "llvm/IR/Instructions.h"
17 : #include "llvm/IR/IntrinsicInst.h"
18 :
19 : using namespace llvm;
20 : using namespace fuzzerop;
21 :
22 11 : Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
23 : ArrayRef<Instruction *> Insts) {
24 11 : return findOrCreateSource(BB, Insts, {}, anyType());
25 : }
26 :
27 82 : Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
28 : ArrayRef<Instruction *> Insts,
29 : ArrayRef<Value *> Srcs,
30 : SourcePred Pred) {
31 : auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) {
32 80 : return Pred.matches(Srcs, Inst);
33 82 : };
34 82 : auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred));
35 : // Also consider choosing no source, meaning we want a new one.
36 82 : RS.sample(nullptr, /*Weight=*/1);
37 82 : if (Instruction *Src = RS.getSelection())
38 : return Src;
39 74 : return newSource(BB, Insts, Srcs, Pred);
40 : }
41 :
42 84 : Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
43 : ArrayRef<Value *> Srcs, SourcePred Pred) {
44 : // Generate some constants to choose from.
45 84 : auto RS = makeSampler<Value *>(Rand);
46 84 : RS.sample(Pred.generate(Srcs, KnownTypes));
47 :
48 : // If we can find a pointer to load from, use it half the time.
49 84 : Value *Ptr = findPointer(BB, Insts, Srcs, Pred);
50 84 : if (Ptr) {
51 : // Create load from the chosen pointer
52 : auto IP = BB.getFirstInsertionPt();
53 : if (auto *I = dyn_cast<Instruction>(Ptr)) {
54 20 : IP = ++I->getIterator();
55 : assert(IP != BB.end() && "guaranteed by the findPointer");
56 : }
57 20 : auto *NewLoad = new LoadInst(Ptr, "L", &*IP);
58 :
59 : // Only sample this load if it really matches the descriptor
60 20 : if (Pred.matches(Srcs, NewLoad))
61 10 : RS.sample(NewLoad, RS.totalWeight());
62 : else
63 10 : NewLoad->eraseFromParent();
64 : }
65 :
66 : assert(!RS.isEmpty() && "Failed to generate sources");
67 84 : return RS.getSelection();
68 : }
69 :
70 30 : static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
71 : const Value *Replacement) {
72 30 : if (Operand->getType() != Replacement->getType())
73 : return false;
74 : switch (I->getOpcode()) {
75 0 : 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 0 : if (Operand.getOperandNo() >= 1)
81 0 : return false;
82 : break;
83 30 : case Instruction::InsertValue:
84 : case Instruction::InsertElement:
85 : case Instruction::ShuffleVector:
86 30 : if (Operand.getOperandNo() >= 2)
87 10 : return false;
88 : break;
89 : default:
90 : break;
91 : }
92 : return true;
93 : }
94 :
95 11 : void RandomIRBuilder::connectToSink(BasicBlock &BB,
96 : ArrayRef<Instruction *> Insts, Value *V) {
97 11 : auto RS = makeSampler<Use *>(Rand);
98 22 : for (auto &I : Insts) {
99 11 : 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 52 : for (Use &U : I->operands())
105 30 : if (isCompatibleReplacement(I, U, V))
106 20 : RS.sample(&U, 1);
107 : }
108 : // Also consider choosing no sink, meaning we want a new one.
109 11 : RS.sample(nullptr, /*Weight=*/1);
110 :
111 11 : if (Use *Sink = RS.getSelection()) {
112 8 : User *U = Sink->getUser();
113 8 : unsigned OpNo = Sink->getOperandNo();
114 8 : U->setOperand(OpNo, V);
115 8 : return;
116 : }
117 3 : newSink(BB, Insts, V);
118 : }
119 :
120 3 : void RandomIRBuilder::newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts,
121 : Value *V) {
122 3 : Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType());
123 3 : if (!Ptr) {
124 3 : if (uniform(Rand, 0, 1))
125 4 : Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt());
126 : else
127 1 : Ptr = UndefValue::get(PointerType::get(V->getType(), 0));
128 : }
129 :
130 6 : new StoreInst(V, Ptr, Insts.back());
131 3 : }
132 :
133 87 : 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 87 : };
153 87 : if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
154 20 : return RS.getSelection();
155 67 : return nullptr;
156 : }
|
