[FuzzMutate] InsertFunctionStrategy

[Peter]

Summary

InsertFunctionStrategy does two things:

1. Add a random function declaration or definition to the module. This would replace previously used createEmptyFunction.
2. Add a random function call between instructions.

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

346

Don't see the point of the initializer here

359

arg_empty

[Peter]

use arg_empty

[Peter]

update

[Peter]

[FuzzMutate] InsertFunctionStrategy

InsertFunctionStrategy does two things:

Add a random function declaration or definition to the module. This would replace previously used createEmptyFunction.
Add a random function call between instructions.

[Peter]

sync with upstream

[Peter]

llvm/lib/FuzzMutate/IRMutator.cpp

346

If the mutator select nullptr, we can create a new function. This is to give us a chance to define more functions.

359

Fixed, thanks for pointint out.

[Peter]

sync with upstream

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

374

Can use make_range(BB.getFirstInsertionPt(), BB.end())

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

426

Missing alloca address space

[Peter]

use make range and add address space

[Peter]

update

llvm/include/llvm/FuzzMutate/IRMutator.h

uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
                      uint64_t CurrentWeight) override {
     return 4;
   }
 
   using IRMutationStrategy::mutate;
   void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
 };
 
+/// Strategy that generates new function calls and inserts function signatures
+/// to the modules. If any signatures are present in the module it will be
+/// called.
+class InsertFunctionStrategy : public IRMutationStrategy {
+public:
+  uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
+                     uint64_t CurrentWeight) override {
+    return 10;
+  }
+
+  using IRMutationStrategy::mutate;
+  void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
+};
+
 /// Strategy to split a random block and insert a random CFG in between.
 class InsertCFGStrategy : public IRMutationStrategy {
 private:
   uint64_t MaxNumCases;
   enum CFGToSink { Return, DirectSink, SinkOrSelfLoop, EndOfCFGToLink };
 
 public:
   InsertCFGStrategy(uint64_t MNC = 8) : MaxNumCases(MNC){};

llvm/include/llvm/FuzzMutate/RandomIRBuilder.h

 
 namespace llvm {
 class AllocaInst;
 class BasicBlock;
 class Function;
 class GlobalVariable;
 class Instruction;
 class LLVMContext;
+class Module;
 class Type;
 class Value;
-class Module;
 
 namespace fuzzerop {
 class SourcePred;
 }
 
 using RandomEngine = std::mt19937;
 
 struct RandomIRBuilder {
   RandomEngine Rand;
   SmallVector<Type *, 16> KnownTypes;
 
+  uint64_t MinArgNum = 0;
+  uint64_t MaxArgNum = 5;
+  uint64_t MinFunctionNum = 1;
+
   RandomIRBuilder(int Seed, ArrayRef<Type *> AllowedTypes)
       : Rand(Seed), KnownTypes(AllowedTypes.begin(), AllowedTypes.end()) {}
 
   // TODO: Try to make this a bit less of a random mishmash of functions.
 
   /// Create a stack memory at the head of the function, store \c Init to the
   /// memory if provided.
   AllocaInst *createStackMemory(Function *F, Type *Ty, Value *Init = nullptr);
struct RandomIRBuilder {
   /// Create a user for \c V in \c BB.
   Instruction *newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, Value *V);
   Value *findPointer(BasicBlock &BB, ArrayRef<Instruction *> Insts,
                      ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred);
   Type *chooseType(LLVMContext &Context, ArrayRef<Value *> Srcs,
                    fuzzerop::SourcePred Pred);
   /// Return a uniformly choosen type from \c AllowedTypes
   Type *randomType();
+  Function *createFunctionDeclaration(Module &M, uint64_t ArgNum);
+  Function *createFunctionDeclaration(Module &M);
+  Function *createFunctionDefinition(Module &M, uint64_t ArgNum);
+  Function *createFunctionDefinition(Module &M);
 };
 
 } // namespace llvm
 
 #endif // LLVM_FUZZMUTATE_RANDOMIRBUILDER_H

llvm/lib/FuzzMutate/IRMutator.cpp

 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Transforms/Scalar/DCE.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include <optional>
 
 using namespace llvm;
 
-static void createEmptyFunction(Module &M) {
-  // TODO: Some arguments and a return value would probably be more interesting.
-  LLVMContext &Context = M.getContext();
-  Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {},
-                                                   /*isVarArg=*/false),
-                                 GlobalValue::ExternalLinkage, "f", &M);
-  BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
-  ReturnInst::Create(Context, BB);
-}
-
 void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
   auto RS = makeSampler<Function *>(IB.Rand);
   for (Function &F : M)
     if (!F.isDeclaration())
       RS.sample(&F, /*Weight=*/1);
 
-  if (RS.isEmpty())
-    createEmptyFunction(M);
-  else
-    mutate(*RS.getSelection(), IB);
+  while (RS.totalWeight() < IB.MinFunctionNum) {
+    Function *F = IB.createFunctionDefinition(M);
+    RS.sample(F, /*Weight=*/1);
+  }
 }
 
 void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
   mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
 }
 
 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
   mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
static uint64_t getUniqueCaseValue(SmallSet<uint64_t, 4> &CasesTaken,
   uint64_t tmp;
   do {
     tmp = uniform<uint64_t>(IB.Rand, 0, MaxValue);
   } while (CasesTaken.count(tmp) != 0);
   CasesTaken.insert(tmp);
   return tmp;
 }
 
+void InsertFunctionStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
+  Module *M = BB.getParent()->getParent();
+  // If nullptr is selected, we will create a new function declaration.
+  SmallVector<Function *, 32> Functions({nullptr});
+  for (Function &F : M->functions()) {
+    Functions.push_back(&F);
+  }
+
+  auto RS = makeSampler(IB.Rand, Functions);
+  Function *F = RS.getSelection();
+  if (!F) {
+    F = IB.createFunctionDeclaration(*M);
+  }
+
+  FunctionType *FTy = F->getFunctionType();
+  SmallVector<fuzzerop::SourcePred, 2> SourcePreds;
+  if (!F->arg_empty()) {
+    for (Type *ArgTy : FTy->params()) {
+      SourcePreds.push_back(fuzzerop::onlyType(ArgTy));
+    }
+  }
+  bool isRetVoid = (F->getReturnType() == Type::getVoidTy(M->getContext()));
+  auto BuilderFunc = [FTy, F, isRetVoid](ArrayRef<Value *> Srcs,
+                                         Instruction *Inst) {
+    StringRef Name = isRetVoid ? nullptr : "C";
+    CallInst *Call = CallInst::Create(FTy, F, Srcs, Name, Inst);
+    // Don't return this call inst if it return void as it can't be sinked.
+    return isRetVoid ? nullptr : Call;
+  };
+
+  SmallVector<Instruction *, 32> Insts;
+  for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
+    Insts.push_back(&I);
+  if (Insts.size() < 1)
+    return;
+
+  // Choose an insertion point for our new call instruction.
+  uint64_t IP = uniform<uint64_t>(IB.Rand, 0, Insts.size() - 1);
+
+  auto InstsBefore = ArrayRef(Insts).slice(0, IP);
+  auto InstsAfter = ArrayRef(Insts).slice(IP);
+
+  // Choose a source, which will be used to constrain the operation selection.
+  SmallVector<Value *, 2> Srcs;
+
+  for (const auto &Pred : ArrayRef(SourcePreds)) {
+    Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
+  }
+
+  if (Value *Op = BuilderFunc(Srcs, Insts[IP])) {
+    // Find a sink and wire up the results of the operation.
+    IB.connectToSink(BB, InstsAfter, Op);
+  }
+}
+
 void InsertCFGStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
   SmallVector<Instruction *, 32> Insts;
-  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
-    Insts.push_back(&*I);
+  for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
+    Insts.push_back(&I);
   if (Insts.size() < 1)
     return;
 
   // Choose a point where we split the block.
   uint64_t IP = uniform<uint64_t>(IB.Rand, 0, Insts.size() - 1);
   auto InstsBeforeSplit = ArrayRef(Insts).slice(0, IP);
 
   // `Sink` inherits Blocks' terminator, `Source` will have a BranchInst
if (!Src) {
       // There is no need to inform IB what previously used values are if we are
       // using `onlyType`
       Src = IB.findOrCreateSource(*Pred, Insts, {}, fuzzerop::onlyType(Ty));
       IncomingValues[Pred] = Src;
     }
     PHI->addIncoming(Src, Pred);
   }
   SmallVector<Instruction *, 32> InstsAfter;
-  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
-    InstsAfter.push_back(&*I);
+  for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
+    InstsAfter.push_back(&I);
   IB.connectToSink(BB, InstsAfter, PHI);
 }
 
 void SinkInstructionStrategy::mutate(Function &F, RandomIRBuilder &IB) {
   for (BasicBlock &BB : F) {
     this->mutate(BB, IB);
   }
 }
 void SinkInstructionStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
   SmallVector<Instruction *, 32> Insts;
-  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
-    Insts.push_back(&*I);
+  for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end()))
+    Insts.push_back(&I);
   if (Insts.size() < 1)
     return;
   // Choose an Instruction to mutate.
   uint64_t Idx = uniform<uint64_t>(IB.Rand, 0, Insts.size() - 1);
   Instruction *Inst = Insts[Idx];
   // `Idx + 1` so we don't sink to ourselves.
   auto InstsAfter = ArrayRef(Insts).slice(Idx + 1);
   LLVMContext &C = BB.getParent()->getParent()->getContext();

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
     return RS.getSelection();
   return nullptr;
 }
 
 Type *RandomIRBuilder::randomType() {
   uint64_t TyIdx = uniform<uint64_t>(Rand, 0, KnownTypes.size() - 1);
   return KnownTypes[TyIdx];
 }
+
+Function *RandomIRBuilder::createFunctionDeclaration(Module &M,
+                                                     uint64_t ArgNum) {
+  Type *RetType = randomType();
+
+  SmallVector<Type *, 2> Args;
+  for (uint64_t i = 0; i < ArgNum; i++) {
+    Args.push_back(randomType());
+  }
+
+  Function *F = Function::Create(FunctionType::get(RetType, Args,
+                                                   /*isVarArg=*/false),
+                                 GlobalValue::ExternalLinkage, "f", &M);
+  return F;
+}
+Function *RandomIRBuilder::createFunctionDeclaration(Module &M) {
+  return createFunctionDeclaration(
+      M, uniform<uint64_t>(Rand, MinArgNum, MaxArgNum));
+}
+
+Function *RandomIRBuilder::createFunctionDefinition(Module &M,
+                                                    uint64_t ArgNum) {
+  Function *F = this->createFunctionDeclaration(M, ArgNum);
+
+  // TODO: Some arguments and a return value would probably be more
+  // interesting.
+  LLVMContext &Context = M.getContext();
+  DataLayout DL(&M);
+  BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
+  Type *RetTy = F->getReturnType();
+  if (RetTy != Type::getVoidTy(Context)) {
+    Instruction *RetAlloca =
+        new AllocaInst(RetTy, DL.getAllocaAddrSpace(), "RP", BB);
+    Instruction *RetLoad = new LoadInst(RetTy, RetAlloca, "", BB);
+    ReturnInst::Create(Context, RetLoad, BB);
+  } else {
+    ReturnInst::Create(Context, BB);
+  }
+
+  return F;
+}
+Function *RandomIRBuilder::createFunctionDefinition(Module &M) {
+  return createFunctionDefinition(
+      M, uniform<uint64_t>(Rand, MinArgNum, MaxArgNum));
+}

llvm/unittests/FuzzMutate/StrategiesTest.cpp

 TEST(InstModificationIRStrategyTest, DidntShuffleFRem) {
   StringRef Source = "\n\
       define <2 x double> @test(<2 x double> %0) {\n\
         %div = frem <2 x double> <double 0.0, double 0.0>, %0\n\
         ret <2 x double> %div\n\
       }";
   VerfyDivDidntShuffle(Source);
 }
+
+TEST(FunctionIRStrategy, Func) {
+  LLVMContext Ctx;
+  const char *Source = "";
+  auto Mutator = createMutator<InsertFunctionStrategy>();
+  ASSERT_TRUE(Mutator);
+
+  auto M = parseAssembly(Source, Ctx);
+  srand(Seed);
+  for (int i = 0; i < 100; i++) {
+    Mutator->mutateModule(*M, rand(), 0, 1024);
+    EXPECT_TRUE(!verifyModule(*M, &errs()));
+  }
+}
+
 TEST(InstModificationIRStrategy, Exact) {
   LLVMContext Ctx;
   StringRef Source = "\n\
       define i32 @test(i32 %a, i32 %b) {\n\
         %c = ashr i32 %a, %b \n\
         ret i32 %c\n\
       }";