contrib/llvm/lib/FuzzMutate/IRMutator.cpp

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