LCOV - code coverage report
Current view: top level - lib/FuzzMutate - IRMutator.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 78 102 76.5 %
Date: 2018-09-23 13:06:45 Functions: 11 13 84.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13