[FuzzMutate] Module size heuristics

[oakrc]

Summary

IRMutation::mutateModule() currently requires the bitcode size of the module.
To compute the bitcode size, one way is to write the module to a buffer using
BitcodeWriter and calculating the buffer size. This would be fine for a single
mutation, but infeasible for repeated mutations due to the large overhead. It
turns out that the only IR strategy weight calculation method that depends on
the current module size is InstDeleterStrategy, which deletes instructions more
frequently as the module size approaches a given max size. However, there is no
real need for the size to be in bytes of bitcode, so we can use a different
metric. One alternative is to let the size be the number of objects in the
Module, including instructions, basic blocks, globals, and aliases. Although
getting the number of instructions is still O(n), it should have significantly
less overhead than BitcodeWriter. This suggestion would cause a change to the
IRMutator API, since IRMutator::mutateModule() can calculate the Module size
itself.

[Peter]

llvm/include/llvm/FuzzMutate/IRMutator.h

74

Can you add comments here about the change and the semantics of size?

[oakrc]

Fix usage of IRMutator::mutateModule in llvm-isel-fuzzer. MaxSize provided is
in bytes of bitcode but we can give it to IRMutator as a reference. writeModule
will silently refuse to save new module if actual bitcode size exceeds MaxSize.

[oakrc]

Add comments to clarify the meaning of getModuleSize and MaxSize.

[oakrc]

Fix another usage in llvm-opt-fuzzer. Did a recursive grep and there should be
no other usage left.

llvm/include/llvm/FuzzMutate/IRMutator.h

class IRMutator {
   std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
 
 public:
   IRMutator(std::vector<TypeGetter> &&AllowedTypes,
             std::vector<std::unique_ptr<IRMutationStrategy>> &&Strategies)
       : AllowedTypes(std::move(AllowedTypes)),
         Strategies(std::move(Strategies)) {}
 
-  void mutateModule(Module &M, int Seed, size_t CurSize, size_t MaxSize);
+  static size_t getModuleSize(const Module &M);
+  void mutateModule(Module &M, int Seed, size_t MaxSize);
 };
 
 /// Strategy that injects operations into the function.
 class InjectorIRStrategy : public IRMutationStrategy {
   std::vector<fuzzerop::OpDescriptor> Operations;
 
   std::optional<fuzzerop::OpDescriptor> chooseOperation(Value *Src,
                                                         RandomIRBuilder &IB);

llvm/lib/FuzzMutate/IRMutator.cpp

void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
 
   mutate(*makeSampler(IB.Rand, Range).getSelection(), IB);
 }
 
 void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
   mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
 }
 
-void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
-                             size_t MaxSize) {
+size_t llvm::IRMutator::getModuleSize(const Module &M) {
+  return M.getInstructionCount() + M.size() + M.global_size() + M.alias_size();
+}
+
+void IRMutator::mutateModule(Module &M, int Seed, size_t MaxSize) {
   std::vector<Type *> Types;
   for (const auto &Getter : AllowedTypes)
     Types.push_back(Getter(M.getContext()));
   RandomIRBuilder IB(Seed, Types);
 
+  size_t CurSize = IRMutator::getModuleSize(M);
   auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
   for (const auto &Strategy : Strategies)
     RS.sample(Strategy.get(),
               Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
+  if (RS.totalWeight() == 0)
+    return;
   auto Strategy = RS.getSelection();
 
   Strategy->mutate(M, IB);
 }
 
 static void eliminateDeadCode(Function &F) {
   FunctionPassManager FPM;
   FPM.addPass(DCEPass());

llvm/unittests/FuzzMutate/StrategiesTest.cpp

 
 void IterateOnSource(StringRef Source, IRMutator &Mutator) {
   LLVMContext Ctx;
 
   for (int i = 0; i < 10; ++i) {
     auto M = parseAssembly(Source.data(), Ctx);
     ASSERT_TRUE(M && !verifyModule(*M, &errs()));
 
-    Mutator.mutateModule(*M, Seed, Source.size(), Source.size() + 100);
+    Mutator.mutateModule(*M, Seed, IRMutator::getModuleSize(*M) + 100);
     EXPECT_TRUE(!verifyModule(*M, &errs()));
   }
 }
 
 static void mutateAndVerifyModule(StringRef Source,
                                   std::unique_ptr<IRMutator> &Mutator,
                                   int repeat = 100) {
   LLVMContext Ctx;
   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);
+    Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 1024);
     ASSERT_FALSE(verifyModule(*M, &errs()));
   }
 }
 template <class Strategy>
 static void mutateAndVerifyModule(StringRef Source, int repeat = 100) {
   auto Mutator = createMutator<Strategy>();
   ASSERT_TRUE(Mutator);
   mutateAndVerifyModule(Source, Mutator, repeat);
 }
 
 TEST(InjectorIRStrategyTest, EmptyModule) {
   // Test that we can inject into empty module
 
   LLVMContext Ctx;
   auto M = std::make_unique<Module>("M", Ctx);
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
 
   auto Mutator = createInjectorMutator();
   ASSERT_TRUE(Mutator);
 
-  Mutator->mutateModule(*M, Seed, 1, 1);
+  Mutator->mutateModule(*M, Seed, IRMutator::getModuleSize(*M) + 1);
   EXPECT_TRUE(!verifyModule(*M, &errs()));
 }
 
 TEST(InjectorIRStrategyTest, LargeInsertion) {
   StringRef Source = "";
   auto Mutator = createInjectorMutator();
   ASSERT_TRUE(Mutator);
   mutateAndVerifyModule(Source, Mutator, 100);
static void checkModifyNoUnsignedAndNoSignedWrap(StringRef Opc) {
 
   auto M = parseAssembly(Source.data(), Ctx);
   auto &F = *M->begin();
   auto *AddI = &*F.begin()->begin();
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
   bool FoundNUW = false;
   bool FoundNSW = false;
   for (int i = 0; i < 100; ++i) {
-    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
     EXPECT_TRUE(!verifyModule(*M, &errs()));
     FoundNUW |= AddI->hasNoUnsignedWrap();
     FoundNSW |= AddI->hasNoSignedWrap();
   }
 
   // The mutator should have added nuw and nsw during some mutations.
   EXPECT_TRUE(FoundNUW);
   EXPECT_TRUE(FoundNSW);
TEST(InstModificationIRStrategyTest, ICmp) {
   ASSERT_TRUE(Mutator);
 
   auto M = parseAssembly(Source.data(), Ctx);
   auto &F = *M->begin();
   CmpInst *CI = cast<CmpInst>(&*F.begin()->begin());
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
   bool FoundNE = false;
   for (int i = 0; i < 100; ++i) {
-    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
     EXPECT_TRUE(!verifyModule(*M, &errs()));
     FoundNE |= CI->getPredicate() == CmpInst::ICMP_NE;
   }
 
   EXPECT_TRUE(FoundNE);
 }
 
 TEST(InstModificationIRStrategyTest, FCmp) {
   LLVMContext Ctx;
   StringRef Source = "\n\
       define i1 @test(float %x) {\n\
         %a = fcmp oeq float %x, 10.0\n\
         ret i1 %a\n\
       }";
 
   auto Mutator = createMutator<InstModificationIRStrategy>();
   ASSERT_TRUE(Mutator);
 
   auto M = parseAssembly(Source.data(), Ctx);
   auto &F = *M->begin();
   CmpInst *CI = cast<CmpInst>(&*F.begin()->begin());
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
   bool FoundONE = false;
   for (int i = 0; i < 100; ++i) {
-    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
     EXPECT_TRUE(!verifyModule(*M, &errs()));
     FoundONE |= CI->getPredicate() == CmpInst::FCMP_ONE;
   }
 
   EXPECT_TRUE(FoundONE);
 }
 
 TEST(InstModificationIRStrategyTest, GEP) {
   LLVMContext Ctx;
   StringRef Source = "\n\
       define i32* @test(i32* %ptr) {\n\
         %gep = getelementptr i32, i32* %ptr, i32 10\n\
         ret i32* %gep\n\
       }";
 
   auto Mutator = createMutator<InstModificationIRStrategy>();
   ASSERT_TRUE(Mutator);
 
   auto M = parseAssembly(Source.data(), Ctx);
   auto &F = *M->begin();
   GetElementPtrInst *GEP = cast<GetElementPtrInst>(&*F.begin()->begin());
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
   bool FoundInbounds = false;
   for (int i = 0; i < 100; ++i) {
-    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    Mutator->mutateModule(*M, Seed + i, IRMutator::getModuleSize(*M) + 100);
     EXPECT_TRUE(!verifyModule(*M, &errs()));
     FoundInbounds |= GEP->isInBounds();
   }
 
   EXPECT_TRUE(FoundInbounds);
 }
 
 /// The caller has to guarantee that function argument are used in the SAME
 /// place as the operand.
 void VerfyOperandShuffled(StringRef Source, std::pair<int, int> ShuffleItems) {
   LLVMContext Ctx;
   auto Mutator = createMutator<InstModificationIRStrategy>();
   ASSERT_TRUE(Mutator);
 
   auto M = parseAssembly(Source.data(), Ctx);
   auto &F = *M->begin();
   Instruction *Inst = &*F.begin()->begin();
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
   ASSERT_TRUE(Inst->getOperand(ShuffleItems.first) ==
               dyn_cast<Value>(F.getArg(ShuffleItems.first)));
   ASSERT_TRUE(Inst->getOperand(ShuffleItems.second) ==
               dyn_cast<Value>(F.getArg(ShuffleItems.second)));
 
-  Mutator->mutateModule(*M, 0, Source.size(), Source.size() + 100);
+  Mutator->mutateModule(*M, 0, IRMutator::getModuleSize(*M) + 100);
   ASSERT_TRUE(!verifyModule(*M, &errs()));
 
   ASSERT_TRUE(Inst->getOperand(ShuffleItems.first) ==
               dyn_cast<Value>(F.getArg(ShuffleItems.second)));
   ASSERT_TRUE(Inst->getOperand(ShuffleItems.second) ==
               dyn_cast<Value>(F.getArg(ShuffleItems.first)));
 }
 
void VerfyDivDidntShuffle(StringRef Source) {
   auto M = parseAssembly(Source.data(), Ctx);
   auto &F = *M->begin();
   Instruction *Inst = &*F.begin()->begin();
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
 
   EXPECT_TRUE(isa<Constant>(Inst->getOperand(0)));
   EXPECT_TRUE(Inst->getOperand(1) == dyn_cast<Value>(F.getArg(0)));
 
-  Mutator->mutateModule(*M, Seed, Source.size(), Source.size() + 100);
+  Mutator->mutateModule(*M, Seed, IRMutator::getModuleSize(*M) + 100);
   EXPECT_TRUE(!verifyModule(*M, &errs()));
 
   // Didn't shuffle.
   EXPECT_TRUE(isa<Constant>(Inst->getOperand(0)));
   EXPECT_TRUE(Inst->getOperand(1) == dyn_cast<Value>(F.getArg(0)));
 }
 TEST(InstModificationIRStrategyTest, DidntShuffleSDiv) {
   StringRef Source = "\n\
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);
+    Mutator->mutateModule(*M, rand(), 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\
       }";
 
   auto Mutator = createMutator<InstModificationIRStrategy>();
   ASSERT_TRUE(Mutator);
 
   std::unique_ptr<Module> M = parseAssembly(Source.data(), Ctx);
   std::mt19937 mt(Seed);
   std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
   auto &F = *M->begin();
   BinaryOperator *AShr = cast<BinaryOperator>(&*F.begin()->begin());
   bool FoundExact = false;
   for (int i = 0; i < 100; ++i) {
-    Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 100);
+    Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 100);
     ASSERT_FALSE(verifyModule(*M, &errs()));
     FoundExact |= AShr->isExact();
   }
 
   EXPECT_TRUE(FoundExact);
 }
 TEST(InstModificationIRStrategy, FastMath) {
   LLVMContext Ctx;
for (auto &BB : F) {
         if (Ty->isFPOrFPVectorTy() || Ty->isArrayTy()) {
           FPOpsHasFastMath[&I] = false;
         }
       }
     }
   }
   ASSERT_TRUE(M && !verifyModule(*M, &errs()));
   for (int i = 0; i < 300; ++i) {
-    Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 100);
+    Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 100);
     for (auto p : FPOpsHasFastMath)
       FPOpsHasFastMath[p.first] |= p.first->getFastMathFlags().any();
     ASSERT_FALSE(verifyModule(*M, &errs()));
   }
   for (auto p : FPOpsHasFastMath)
     ASSERT_TRUE(p.second);
 }
 
static void VerifyBlockShuffle(StringRef Source) {
   Function *F = &*M->begin();
   DenseMap<BasicBlock *, int> PreShuffleInstCnt;
   for (BasicBlock &BB : *F) {
     PreShuffleInstCnt.insert({&BB, BB.size()});
   }
   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);
+    Mutator->mutateModule(*M, RandInt(mt), IRMutator::getModuleSize(*M) + 1024);
     for (BasicBlock &BB : *F) {
       int PostShuffleIntCnt = BB.size();
       EXPECT_EQ(PostShuffleIntCnt, PreShuffleInstCnt[&BB]);
     }
     EXPECT_FALSE(verifyModule(*M, &errs()));
   }
 }