1//===-- IRMutator.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/IRMutator.h"
10#include "llvm/ADT/Optional.h"
11#include "llvm/Analysis/TargetLibraryInfo.h"
12#include "llvm/FuzzMutate/Operations.h"
13#include "llvm/FuzzMutate/Random.h"
14#include "llvm/FuzzMutate/RandomIRBuilder.h"
15#include "llvm/IR/BasicBlock.h"
16#include "llvm/IR/Function.h"
17#include "llvm/IR/InstIterator.h"
18#include "llvm/IR/Instructions.h"
19#include "llvm/IR/Module.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Transforms/Scalar/DCE.h"
22
23using namespace llvm;
24
25static void createEmptyFunction(Module &M) {
26  // TODO: Some arguments and a return value would probably be more interesting.
27  LLVMContext &Context = M.getContext();
28  Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {},
29                                                   /*isVarArg=*/false),
30                                 GlobalValue::ExternalLinkage, "f", &M);
31  BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
32  ReturnInst::Create(Context, BB);
33}
34
35void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
36  if (M.empty())
37    createEmptyFunction(M);
38
39  auto RS = makeSampler<Function *>(IB.Rand);
40  for (Function &F : M)
41    if (!F.isDeclaration())
42      RS.sample(&F, /*Weight=*/1);
43  mutate(*RS.getSelection(), IB);
44}
45
46void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
47  mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
48}
49
50void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
51  mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
52}
53
54void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
55                             size_t MaxSize) {
56  std::vector<Type *> Types;
57  for (const auto &Getter : AllowedTypes)
58    Types.push_back(Getter(M.getContext()));
59  RandomIRBuilder IB(Seed, Types);
60
61  auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
62  for (const auto &Strategy : Strategies)
63    RS.sample(Strategy.get(),
64              Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
65  auto Strategy = RS.getSelection();
66
67  Strategy->mutate(M, IB);
68}
69
70static void eliminateDeadCode(Function &F) {
71  FunctionPassManager FPM;
72  FPM.addPass(DCEPass());
73  FunctionAnalysisManager FAM;
74  FAM.registerPass([&] { return TargetLibraryAnalysis(); });
75  FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
76  FPM.run(F, FAM);
77}
78
79void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
80  IRMutationStrategy::mutate(F, IB);
81  eliminateDeadCode(F);
82}
83
84std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
85  std::vector<fuzzerop::OpDescriptor> Ops;
86  describeFuzzerIntOps(Ops);
87  describeFuzzerFloatOps(Ops);
88  describeFuzzerControlFlowOps(Ops);
89  describeFuzzerPointerOps(Ops);
90  describeFuzzerAggregateOps(Ops);
91  describeFuzzerVectorOps(Ops);
92  return Ops;
93}
94
95Optional<fuzzerop::OpDescriptor>
96InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
97  auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
98    return Op.SourcePreds[0].matches({}, Src);
99  };
100  auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
101  if (RS.isEmpty())
102    return None;
103  return *RS;
104}
105
106void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
107  SmallVector<Instruction *, 32> Insts;
108  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
109    Insts.push_back(&*I);
110  if (Insts.size() < 1)
111    return;
112
113  // Choose an insertion point for our new instruction.
114  size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
115
116  auto InstsBefore = makeArrayRef(Insts).slice(0, IP);
117  auto InstsAfter = makeArrayRef(Insts).slice(IP);
118
119  // Choose a source, which will be used to constrain the operation selection.
120  SmallVector<Value *, 2> Srcs;
121  Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore));
122
123  // Choose an operation that's constrained to be valid for the type of the
124  // source, collect any other sources it needs, and then build it.
125  auto OpDesc = chooseOperation(Srcs[0], IB);
126  // Bail if no operation was found
127  if (!OpDesc)
128    return;
129
130  for (const auto &Pred : makeArrayRef(OpDesc->SourcePreds).slice(1))
131    Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
132
133  if (Value *Op = OpDesc->BuilderFunc(Srcs, Insts[IP])) {
134    // Find a sink and wire up the results of the operation.
135    IB.connectToSink(BB, InstsAfter, Op);
136  }
137}
138
139uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize,
140                                          uint64_t CurrentWeight) {
141  // If we have less than 200 bytes, panic and try to always delete.
142  if (CurrentSize > MaxSize - 200)
143    return CurrentWeight ? CurrentWeight * 100 : 1;
144  // Draw a line starting from when we only have 1k left and increasing linearly
145  // to double the current weight.
146  int Line = (-2 * CurrentWeight) * (MaxSize - CurrentSize + 1000);
147  // Clamp negative weights to zero.
148  if (Line < 0)
149    return 0;
150  return Line;
151}
152
153void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
154  auto RS = makeSampler<Instruction *>(IB.Rand);
155  for (Instruction &Inst : instructions(F)) {
156    // TODO: We can't handle these instructions.
157    if (Inst.isTerminator() || Inst.isEHPad() ||
158        Inst.isSwiftError() || isa<PHINode>(Inst))
159      continue;
160
161    RS.sample(&Inst, /*Weight=*/1);
162  }
163  if (RS.isEmpty())
164    return;
165
166  // Delete the instruction.
167  mutate(*RS.getSelection(), IB);
168  // Clean up any dead code that's left over after removing the instruction.
169  eliminateDeadCode(F);
170}
171
172void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
173  assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
174
175  if (Inst.getType()->isVoidTy()) {
176    // Instructions with void type (ie, store) have no uses to worry about. Just
177    // erase it and move on.
178    Inst.eraseFromParent();
179    return;
180  }
181
182  // Otherwise we need to find some other value with the right type to keep the
183  // users happy.
184  auto Pred = fuzzerop::onlyType(Inst.getType());
185  auto RS = makeSampler<Value *>(IB.Rand);
186  SmallVector<Instruction *, 32> InstsBefore;
187  BasicBlock *BB = Inst.getParent();
188  for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
189       ++I) {
190    if (Pred.matches({}, &*I))
191      RS.sample(&*I, /*Weight=*/1);
192    InstsBefore.push_back(&*I);
193  }
194  if (!RS)
195    RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
196
197  Inst.replaceAllUsesWith(RS.getSelection());
198  Inst.eraseFromParent();
199}
200