[FuzzMutate] SinkInstructionStrategy

[Peter]

Summary

Randomlly select an instruction and try to use it in the future by replacing it with another instruction's operand.

[Peter]

minor change

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 select a random instruction and add a new sink (user) to it to
+/// increate data dependency.
+class SinkInstructionStrategy : public IRMutationStrategy {
+public:
+  uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
+                     uint64_t CurrentWeight) override {
+    return 2;
+  }
+
+  void mutate(Function &F, RandomIRBuilder &IB) override;
+  void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
+};
+
 /// Strategy to randomly select a block and shuffle the operations without
 /// affecting data dependency.
 class ShuffleBlockStrategy : public IRMutationStrategy {
 public:
   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
                      uint64_t CurrentWeight) override {
     return 2;
   }

llvm/lib/FuzzMutate/IRMutator.cpp

if (ShuffleItems != NoneItem) {
     });
   }
 
   auto RS = makeSampler(IB.Rand, Modifications);
   if (RS)
     RS.getSelection()();
 }
 
+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);
+  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 = makeArrayRef(Insts).slice(Idx + 1);
+  LLVMContext &C = BB.getParent()->getParent()->getContext();
+  // Don't sink terminators, void function calls, etc.
+  if (Inst->getType() != Type::getVoidTy(C))
+    // Find a new sink and wire up the results of the operation.
+    IB.connectToSink(BB, InstsAfter, Inst);
+}
+
 void ShuffleBlockStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
 
   SmallPtrSet<Instruction *, 8> AliveInsts;
   for (auto &I : make_early_inc_range(make_range(
            BB.getFirstInsertionPt(), BB.getTerminator()->getIterator()))) {
     // First gather all instructions that can be shuffled. Don't take
     // terminator.
     AliveInsts.insert(&I);

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(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()));
+  }
+}
+
 static void VerifyBlockShuffle(StringRef Source) {
   LLVMContext Ctx;
   auto Mutator = createMutator<ShuffleBlockStrategy>();
   ASSERT_TRUE(Mutator);
 
   std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx);
   Function *F = &*M->begin();
   DenseMap<BasicBlock *, int> PreShuffleInstCnt;