llvm/lib/FuzzMutate/IRMutator.cpp

   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
  23 using namespace llvm;
  24
  25 static 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
  35 void 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
  46 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
  47   mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
  48 }
  49
  50 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
  51   mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
  52 }
  53
  54 void 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
  70 static 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
  79 void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
  80   IRMutationStrategy::mutate(F, IB);
  81   eliminateDeadCode(F);
  82 }
  83
  84 std::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
  95 Optional<fuzzerop::OpDescriptor>
  96 InjectorIRStrategy::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
 106 void 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
 139 uint64_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   int64_t Line = (-2 * static_cast<int64_t>(CurrentWeight)) *
 147                  (static_cast<int64_t>(MaxSize) -
 148                   static_cast<int64_t>(CurrentSize) - 1000) /
 149                  1000;
 150   // Clamp negative weights to zero.
 151   if (Line < 0)
 152     return 0;
 153   return Line;
 154 }
 155
 156 void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
 157   auto RS = makeSampler<Instruction *>(IB.Rand);
 158   for (Instruction &Inst : instructions(F)) {
 159     // TODO: We can't handle these instructions.
 160     if (Inst.isTerminator() || Inst.isEHPad() ||
 161         Inst.isSwiftError() || isa<PHINode>(Inst))
 162       continue;
 163
 164     RS.sample(&Inst, /*Weight=*/1);
 165   }
 166   if (RS.isEmpty())
 167     return;
 168
 169   // Delete the instruction.
 170   mutate(*RS.getSelection(), IB);
 171   // Clean up any dead code that's left over after removing the instruction.
 172   eliminateDeadCode(F);
 173 }
 174
 175 void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
 176   assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
 177
 178   if (Inst.getType()->isVoidTy()) {
 179     // Instructions with void type (ie, store) have no uses to worry about. Just
 180     // erase it and move on.
 181     Inst.eraseFromParent();
 182     return;
 183   }
 184
 185   // Otherwise we need to find some other value with the right type to keep the
 186   // users happy.
 187   auto Pred = fuzzerop::onlyType(Inst.getType());
 188   auto RS = makeSampler<Value *>(IB.Rand);
 189   SmallVector<Instruction *, 32> InstsBefore;
 190   BasicBlock *BB = Inst.getParent();
 191   for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
 192        ++I) {
 193     if (Pred.matches({}, &*I))
 194       RS.sample(&*I, /*Weight=*/1);
 195     InstsBefore.push_back(&*I);
 196   }
 197   if (!RS)
 198     RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
 199
 200   Inst.replaceAllUsesWith(RS.getSelection());
 201   Inst.eraseFromParent();
 202 }
 203
 204 void InstModificationIRStrategy::mutate(Instruction &Inst,
 205                                         RandomIRBuilder &IB) {
 206   SmallVector<std::function<void()>, 8> Modifications;
 207   CmpInst *CI = nullptr;
 208   GetElementPtrInst *GEP = nullptr;
 209   switch (Inst.getOpcode()) {
 210   default:
 211     break;
 212   case Instruction::Add:
 213   case Instruction::Mul:
 214   case Instruction::Sub:
 215   case Instruction::Shl:
 216     Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(true); }),
 217         Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(false); });
 218     Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(true); });
 219     Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(false); });
 220
 221     break;
 222   case Instruction::ICmp:
 223     CI = cast<ICmpInst>(&Inst);
 224     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_EQ); });
 225     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_NE); });
 226     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGT); });
 227     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGE); });
 228     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULT); });
 229     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULE); });
 230     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGT); });
 231     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGE); });
 232     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLT); });
 233     Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLE); });
 234     break;
 235   case Instruction::GetElementPtr:
 236     GEP = cast<GetElementPtrInst>(&Inst);
 237     Modifications.push_back([GEP]() { GEP->setIsInBounds(true); });
 238     Modifications.push_back([GEP]() { GEP->setIsInBounds(false); });
 239     break;
 240   }
 241
 242   auto RS = makeSampler(IB.Rand, Modifications);
 243   if (RS)
 244     RS.getSelection()();
 245 }