[FuzzMutate] New InsertCFGStrategy

[Peter]

Summary

Mutating CFG is hard as we have to maintain dominator relations.
We avoid this problem by inserting a CFG into a splitted block.

switch, ret, and br instructions are generated.

[Peter]

add more complicate test.

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

341

Don't name the lambda?

344

cast<>? I don't see what RS really is

[Peter]

llvm/lib/FuzzMutate/IRMutator.cpp

344

RS returns a Type*, but because we used a filter isIntegerType, we can be sure that the result must be an IntegerType.

We can add a dynamic cast and check for the sake of readability, but it seems to me its un-necessary runtime overhead.

[Peter]

Update

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

343–344

assert string is a bit weird

346–347

cast<> instead of dyn_cast and assert

365–374

Why is this a lambda here?

406

RetTy->isVoidTy()

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

81

Should query the datalayout address space for new allocas

[Peter]

Query Datalayout before alloca.

[Peter]

llvm/lib/FuzzMutate/IRMutator.cpp

343–344

This is to make sure that when things went wrong, we give some hint to tell the user what's wrong. Is there a recommended way of doing it?

365–374

Just to enclose unnecessary variables(tmp required to make CaseVal unique. I can write the loop outside the lambda if you want to.

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

343–344

I mean the phrasing with the question, and saying "I"

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

365–374

A lambda with no arguments is weird, especially with the placement. Could just be a separate function

[Peter]

update assert string, move lambda as a stand alone function

[arsenm]

lgtm with nits

llvm/lib/FuzzMutate/IRMutator.cpp

311

line after while

317

Can do this in the constructor Insts(BB.getFirstInsertionPt(), BB.end())

355–356

Assert string still weirdly phased

[Peter]

llvm/lib/FuzzMutate/IRMutator.cpp

317

Unfortunately no, BB.getFirstInsertionPt returns an iterator, which can't be implicitly converted to Instruction*

[Peter]

nit fix

[Peter]

nit fix

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 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){};
+  uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
+                     uint64_t CurrentWeight) override {
+    return 5;
+  }
+
+  void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
+
+private:
+  void connectBlocksToSink(ArrayRef<BasicBlock *> Blocks, BasicBlock *Sink,
+                           RandomIRBuilder &IB);
+};
+
 /// Strategy to insert PHI Nodes at the head of each basic block.
 class InsertPHIStrategy : public IRMutationStrategy {
 public:
   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
                      uint64_t CurrentWeight) override {
     return 2;
   }
 

llvm/include/llvm/FuzzMutate/RandomIRBuilder.h

struct RandomIRBuilder {
   /// returns some new arbitrary Value.
   Value *findOrCreateSource(BasicBlock &BB, ArrayRef<Instruction *> Insts);
   /// Find a "source" for some operation, which will be used in one of the
   /// operation's operands. This either selects an instruction in \c Insts that
   /// matches \c Pred, or returns some new Value that matches \c Pred. The
   /// values in \c Srcs should be source operands that have already been
   /// selected.
   Value *findOrCreateSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
-                            ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred);
+                            ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred,
+                            bool allowConstant = true);
   /// Create some Value suitable as a source for some operation.
   Value *newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
-                   ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred);
+                   ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred,
+                   bool allowConstant = true);
   /// Find a viable user for \c V in \c Insts, which should all be contained in
   /// \c BB. This may also create some new instruction in \c BB and use that.
   void connectToSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, Value *V);
   /// Create a user for \c V in \c BB.
   void 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();
 };
 
 } // namespace llvm
 
 #endif // LLVM_FUZZMUTATE_RANDOMIRBUILDER_H

llvm/lib/FuzzMutate/CMakeLists.txt

add_llvm_component_library(LLVMFuzzMutate
   LINK_COMPONENTS
   Analysis
   BitReader
   BitWriter
   Core
   Scalar
   Support
   Target
+  TransformUtils
   )

llvm/lib/FuzzMutate/IRMutator.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Transforms/Scalar/DCE.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 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),
if (ShuffleItems != NoneItem) {
     });
   }
 
   auto RS = makeSampler(IB.Rand, Modifications);
   if (RS)
     RS.getSelection()();
 }
 
+/// Return a case value that is not already taken to make sure we don't have two
+/// cases with same value.
+static uint64_t getUniqueCaseValue(SmallSet<uint64_t, 4> &CasesTaken,
+                                   uint64_t MaxValue, RandomIRBuilder &IB) {
+  uint64_t tmp;
+  do {
+    tmp = uniform<uint64_t>(IB.Rand, 0, MaxValue);
+  } while (CasesTaken.count(tmp) != 0);
+  CasesTaken.insert(tmp);
+  return tmp;
+}
+
+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);
+  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 = makeArrayRef(Insts).slice(0, IP);
+
+  // `Sink` inherits Blocks' terminator, `Source` will have a BranchInst
+  // directly jumps to `Sink`. Here, we have to create a new terminator for
+  // `Source`.
+  BasicBlock *Block = Insts[IP]->getParent();
+  BasicBlock *Source = Block;
+  BasicBlock *Sink = Block->splitBasicBlock(Insts[IP], "BB");
+
+  Function *F = BB.getParent();
+  LLVMContext &C = F->getParent()->getContext();
+  // A coin decides if it is branch or switch
+  if (uniform<uint64_t>(IB.Rand, 0, 1)) {
+    // Branch
+    BasicBlock *IfTrue = BasicBlock::Create(C, "T", F);
+    BasicBlock *IfFalse = BasicBlock::Create(C, "F", F);
+    Value *Cond =
+        IB.findOrCreateSource(*Source, InstsBeforeSplit, {},
+                              fuzzerop::onlyType(Type::getInt1Ty(C)), false);
+    BranchInst *Branch = BranchInst::Create(IfTrue, IfFalse, Cond);
+    // Remove the old terminator.
+    ReplaceInstWithInst(Source->getTerminator(), Branch);
+    // Connect these blocks to `Sink`
+    connectBlocksToSink({IfTrue, IfFalse}, Sink, IB);
+  } else {
+    // Switch
+    // Determine Integer type, it IS possible we use a boolean to switch.
+    auto RS =
+        makeSampler(IB.Rand, make_filter_range(IB.KnownTypes, [](Type *Ty) {
+                      return Ty->isIntegerTy();
+                    }));
+    assert(RS && "There is no integer type in all allowed types, is the "
+                 "setting correct?");
+    Type *Ty = RS.getSelection();
+    IntegerType *IntTy = cast<IntegerType>(Ty);
+
+    uint64_t BitSize = IntTy->getBitWidth();
+    uint64_t MaxCaseVal =
+        (BitSize >= 64) ? (uint64_t)-1 : ((uint64_t)1 << BitSize) - 1;
+    // Create Switch inst in Block
+    Value *Cond = IB.findOrCreateSource(*Source, InstsBeforeSplit, {},
+                                        fuzzerop::onlyType(IntTy), false);
+    BasicBlock *DefaultBlock = BasicBlock::Create(C, "SW_D", F);
+    uint64_t NumCases = uniform<uint64_t>(IB.Rand, 1, MaxNumCases);
+    NumCases = (NumCases > MaxCaseVal) ? MaxCaseVal + 1 : NumCases;
+    SwitchInst *Switch = SwitchInst::Create(Cond, DefaultBlock, NumCases);
+    // Remove the old terminator.
+    ReplaceInstWithInst(Source->getTerminator(), Switch);
+
+    // Create blocks, for each block assign a case value.
+    SmallVector<BasicBlock *, 4> Blocks({DefaultBlock});
+    SmallSet<uint64_t, 4> CasesTaken;
+    for (uint64_t i = 0; i < NumCases; i++) {
+      uint64_t CaseVal = getUniqueCaseValue(CasesTaken, MaxCaseVal, IB);
+      BasicBlock *CaseBlock = BasicBlock::Create(C, "SW_C", F);
+      ConstantInt *OnValue = ConstantInt::get(IntTy, CaseVal);
+      Switch->addCase(OnValue, CaseBlock);
+      Blocks.push_back(CaseBlock);
+    }
+
+    // Connect these blocks to `Sink`
+    connectBlocksToSink(Blocks, Sink, IB);
+  }
+}
+
+/// The caller has to guarantee that these blocks are "empty", i.e. it doesn't
+/// even have terminator.
+void InsertCFGStrategy::connectBlocksToSink(ArrayRef<BasicBlock *> Blocks,
+                                            BasicBlock *Sink,
+                                            RandomIRBuilder &IB) {
+  uint64_t DirectSinkIdx = uniform<uint64_t>(IB.Rand, 0, Blocks.size() - 1);
+  for (uint64_t i = 0; i < Blocks.size(); i++) {
+    // We have at least one block that directly goes to sink.
+    CFGToSink ToSink = (i == DirectSinkIdx)
+                           ? CFGToSink::DirectSink
+                           : static_cast<CFGToSink>(uniform<uint64_t>(
+                                 IB.Rand, 0, CFGToSink::EndOfCFGToLink - 1));
+    BasicBlock *BB = Blocks[i];
+    Function *F = BB->getParent();
+    LLVMContext &C = F->getParent()->getContext();
+    switch (ToSink) {
+    case CFGToSink::Return: {
+      Type *RetTy = F->getReturnType();
+      Value *RetValue = nullptr;
+      if (!RetTy->isVoidTy())
+        RetValue =
+            IB.findOrCreateSource(*BB, {}, {}, fuzzerop::onlyType(RetTy));
+      ReturnInst::Create(C, RetValue, BB);
+      break;
+    }
+    case CFGToSink::DirectSink: {
+      BranchInst::Create(Sink, BB);
+      break;
+    }
+    case CFGToSink::SinkOrSelfLoop: {
+      SmallVector<BasicBlock *, 2> Branches({Sink, BB});
+      // A coin decides which block is true branch.
+      uint64_t coin = uniform<uint64_t>(IB.Rand, 0, 1);
+      Value *Cond = IB.findOrCreateSource(
+          *BB, {}, {}, fuzzerop::onlyType(Type::getInt1Ty(C)), false);
+      BranchInst::Create(Branches[coin], Branches[1 - coin], Cond, BB);
+      break;
+    }
+    case CFGToSink::EndOfCFGToLink:
+      llvm_unreachable("EndOfCFGToLink executed, something's wrong.");
+    }
+  }
+}
+
 void InsertPHIStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
   // Can't insert PHI node to entry node.
   if (&BB == &BB.getParent()->getEntryBlock())
     return;
   Type *Ty = IB.randomType();
   PHINode *PHI = PHINode::Create(Ty, llvm::pred_size(&BB), "", &BB.front());
 
   // Use a map to make sure the same incoming basic block has the same value.

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

 //===-- RandomIRBuilder.cpp -----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/FuzzMutate/RandomIRBuilder.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/FuzzMutate/OpDescriptor.h"
 #include "llvm/FuzzMutate/Random.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 
 using namespace llvm;
 using namespace fuzzerop;
 
 Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
                                            ArrayRef<Instruction *> Insts) {
   return findOrCreateSource(BB, Insts, {}, anyType());
 }
 
 Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
                                            ArrayRef<Instruction *> Insts,
                                            ArrayRef<Value *> Srcs,
-                                           SourcePred Pred) {
+                                           SourcePred Pred,
+                                           bool allowConstant) {
   auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) {
     return Pred.matches(Srcs, Inst);
   };
   auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred));
   // Also consider choosing no source, meaning we want a new one.
   RS.sample(nullptr, /*Weight=*/1);
   if (Instruction *Src = RS.getSelection())
     return Src;
-  return newSource(BB, Insts, Srcs, Pred);
+  return newSource(BB, Insts, Srcs, Pred, allowConstant);
 }
 
 Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
-                                  ArrayRef<Value *> Srcs, SourcePred Pred) {
+                                  ArrayRef<Value *> Srcs, SourcePred Pred,
+                                  bool allowConstant) {
   // Generate some constants to choose from.
   auto RS = makeSampler<Value *>(Rand);
   RS.sample(Pred.generate(Srcs, KnownTypes));
 
   // If we can find a pointer to load from, use it half the time.
   Value *Ptr = findPointer(BB, Insts, Srcs, Pred);
   if (Ptr) {
     // Create load from the chosen pointer
if (Ptr) {
 
     // Only sample this load if it really matches the descriptor
     if (Pred.matches(Srcs, NewLoad))
       RS.sample(NewLoad, RS.totalWeight());
     else
       NewLoad->eraseFromParent();
   }
 
-  assert(!RS.isEmpty() && "Failed to generate sources");
-  return RS.getSelection();
+  Value *newSrc = RS.getSelection();
+  // Generate a stack alloca and store the constant to it if constant is not
+  // allowed, our hope is that later mutations can generate some values and
+  // store to this placeholder.
+  if (!allowConstant && isa<Constant>(newSrc)) {
+    Type *Ty = newSrc->getType();
+    Function *F = BB.getParent();
+    BasicBlock *EntryBB = &F->getEntryBlock();
+    /// TODO: For all Allocas, maybe allocate an array.
+    DataLayout DL(BB.getParent()->getParent());
+    AllocaInst *Alloca = new AllocaInst(Ty, DL.getProgramAddressSpace(), "A",
+                                        EntryBB->getTerminator());
+    new StoreInst(newSrc, Alloca, EntryBB->getTerminator());
+    if (BB.getTerminator()) {
+      newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", BB.getTerminator());
+    } else {
+      newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", &BB);
+    }
+  }
+  return newSrc;
 }
 
 static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
                                     const Value *Replacement) {
   unsigned int OperandNo = Operand.getOperandNo();
   if (Operand->getType() != Replacement->getType())
     return false;
   switch (I->getOpcode()) {

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(InsertPHIStrategy, PHI) {
+template <class Strategy>
+static void mutateAndVerifyModule(StringRef Source, int repeat = 100) {
   LLVMContext Ctx;
+  auto Mutator = createMutator<Strategy>();
+  ASSERT_TRUE(Mutator);
+
+  auto M = parseAssembly(Source.data(), Ctx);
+  std::mt19937 mt(Seed);
+  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
+  for (int i = 0; i < repeat; i++) {
+    Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 1024);
+    ASSERT_FALSE(verifyModule(*M, &errs()));
+  }
+}
+
+TEST(InsertCFGStrategy, CFG) {
+  StringRef Source = "\n\
+      define i32 @test(i1 %C1, i1 %C2, i1 %C3, i16 %S1, i16 %S2, i32 %I1) { \n\
+        Entry:  \n\
+         %I2 = add i32 %I1, 1 \n\
+          %C = and i1 %C1, %C2 \n\
+        br label %Body \n\
+        Body: \n\
+         %IB = add i32 %I1, %I2 \n\
+          %CB = and i1 %C1, %C \n\
+        br label %Exit \n\
+        Exit: \n\
+          %IE = add i32 %IB, %I2 \n\
+          %CE = and i1 %CB, %C \n\
+         ret i32 %IE \n\
+      }";
+  mutateAndVerifyModule<InsertCFGStrategy>(Source);
+}
+
+TEST(InsertPHIStrategy, PHI) {
   StringRef Source = "\n\
         define void @test(i1 %C1, i1 %C2, i32 %I, double %FP) { \n\
         Entry:  \n\
           %C = and i1 %C1, %C2 \n\
           br i1 %C, label %LoopHead, label %Exit \n\
         LoopHead: ; pred Entry, LoopBody \n\
           switch i32 %I, label %Default [ \n\
               i32 1, label %OnOne  \n\
StringRef Source = "\n\
           br i1 %C1, label %OnThree, label %LoopBody \n\
         OnThree: ; pred Entry, OnTwo, OnThree \n\
           br i1 %C2, label %OnThree, label %LoopBody \n\
         LoopBody: ; pred Default, OnOne, OnTwo, OnThree \n\
           br label %LoopHead \n\
         Exit: ; pred Entry, OnOne \n\
           ret void \n\
         }";
-  auto Mutator = createMutator<InsertPHIStrategy>();
-  ASSERT_TRUE(Mutator);
-
-  auto M = parseAssembly(Source.data(), Ctx);
-  std::mt19937 mt(Seed);
-  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
-  for (int i = 0; i < 100; i++) {
-    Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 1024);
-    ASSERT_FALSE(verifyModule(*M, &errs()));
-  }
+  mutateAndVerifyModule<InsertPHIStrategy>(Source);
 }
 
 TEST(InsertPHIStrategy, PHIWithSameIncomingBlock) {
   LLVMContext Ctx;
   StringRef Source = "\n\
         define void @test(i32 %I) { \n\
         Entry:  \n\
           switch i32 %I, label %Exit [ \n\
TEST(InsertPHIStrategy, PHIWithSameIncomingBlock) {
   Function &F = *M->begin();
   for (auto &BB : F) {
     IPS->mutate(BB, IB);
     ASSERT_FALSE(verifyModule(*M, &errs()));
   }
 }
 
 TEST(SinkInstructionStrategy, Operand) {
-  LLVMContext Ctx;
   StringRef Source = "\n\
       define i32 @test(i1 %C1, i1 %C2, i1 %C3, i32 %I, i32 %J) { \n\
         Entry:  \n\
           %I100 = add i32 %I, 100  \n\
           switch i32 %I100, label %BB0 [ \n\
             i32 42, label %BB1  \n\
           ] \n\
         BB0:  \n\
           %IAJ = add i32 %I, %J  \n\
           %ISJ = sub i32 %I, %J  \n\
           br label %Exit  \n\
         BB1:  \n\
           %IJ = mul i32 %I, %J  \n\
           %C = and i1 %C2, %C3  \n\
           br i1 %C, label %BB0, label %Exit  \n\
         Exit:  \n\
           ret i32 %I  \n\
       }";
-  auto Mutator = createMutator<SinkInstructionStrategy>();
-  ASSERT_TRUE(Mutator);
-
-  auto M = parseAssembly(Source.data(), Ctx);
-  std::mt19937 mt(Seed);
-  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
-  for (int i = 0; i < 100; i++) {
-    Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 1024);
-    EXPECT_FALSE(verifyModule(*M, &errs()));
-  }
+  mutateAndVerifyModule<SinkInstructionStrategy>(Source);
 }
 
 static void VerifyBlockShuffle(StringRef Source) {
   LLVMContext Ctx;
   auto Mutator = createMutator<ShuffleBlockStrategy>();
   ASSERT_TRUE(Mutator);
 
   std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx);