[libFuzzer] Optimize handle unstable checks by reducing iterations

[kevinwkt]

Summary

We only run the 3rd check if 2nd check finds unstable edges.
3rd UpdateUnstableCounters is now merged with ApplyUnstableCounters to only run 1 iteration.

Patch by Kyungtak Woo (@kevinwkt).

[Dor1s]

Nice! Do you have an estimate on the performance improvement? The code becomes slightly harder to read, but I guess it's worth it.

lib/fuzzer/FuzzerLoop.cpp

469–473

Just to verify: if we haven't detected any instability, we don't need to apply the counters, right?

[kevinwkt]

In D50411#1191591, @Dor1s wrote:

Nice! Do you have an estimate on the performance improvement? The code becomes slightly harder to read, but I guess it's worth it.

Obviously this would depend on how big and unstable the target is.
Currently, for every new edge we find we run 3x even if it is deterministic.

We would be getting rid of the extra 3rd run for every new deterministic run we find.
Also, since we merged Update and Apply UnstableCounters, we get rid of an iteration for every input that goes through HandleUnstableChecks.

lib/fuzzer/FuzzerLoop.cpp

469–473

Yeah, if we don't detect instability, Inline8bitCounters would be equal to UnstableCounters.

[morehouse]

Nice patch!

[Dor1s]

Rebase and getting ready to land

lib/fuzzer/FuzzerLoop.cpp

auto CBSetupAndRun = [&]() {
     UnitStopTime = system_clock::now();
   };
 
   // Copy original run counters into our unstable counters
   TPC.InitializeUnstableCounters();
 
   // First Rerun
   CBSetupAndRun();
-  TPC.UpdateUnstableCounters(Options.HandleUnstable);
-
+  if (TPC.UpdateUnstableCounters(Options.HandleUnstable)) {
     // Second Rerun
     CBSetupAndRun();
-  TPC.UpdateUnstableCounters(Options.HandleUnstable);
-
-  // Move minimum hit counts back to ModuleInline8bitCounters
-  if (Options.HandleUnstable == TracePC::MinUnstable ||
-      Options.HandleUnstable == TracePC::ZeroUnstable)
-    TPC.ApplyUnstableCounters();
+    TPC.UpdateAndApplyUnstableCounters(Options.HandleUnstable);
+  }
 }
 
 bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                     InputInfo *II, bool *FoundUniqFeatures) {
   if (!Size)
     return false;
 
   ExecuteCallback(Data, Size);

lib/fuzzer/FuzzerTracePC.h

void ForEachObservedPC(CallBack CB) {
     for (auto PC : ObservedPCs)
       CB(PC);
   }
 
   void SetFocusFunction(const std::string &FuncName);
   bool ObservedFocusFunction();
 
   void InitializeUnstableCounters();
-  void UpdateUnstableCounters(int UnstableMode);
-  void ApplyUnstableCounters();
+  bool UpdateUnstableCounters(int UnstableMode);
+  void UpdateAndApplyUnstableCounters(int UnstableMode);
 
 private:
   struct UnstableEdge {
     uint8_t Counter;
     bool IsUnstable;
   };
 
   UnstableEdge UnstableCounters[kNumPCs];

lib/fuzzer/FuzzerTracePC.cpp

 void TracePC::InitializeUnstableCounters() {
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
     UnstableCounters[UnstableIdx].Counter = ModuleCounters[i].Start[j];
   });
 }
 
 // Compares the current counters with counters from previous runs
 // and records differences as unstable edges.
-void TracePC::UpdateUnstableCounters(int UnstableMode) {
+bool TracePC::UpdateUnstableCounters(int UnstableMode) {
+  bool Updated = false;
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
     if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter) {
+      Updated = true;
       UnstableCounters[UnstableIdx].IsUnstable = true;
       if (UnstableMode == ZeroUnstable)
         UnstableCounters[UnstableIdx].Counter = 0;
       else if (UnstableMode == MinUnstable)
         UnstableCounters[UnstableIdx].Counter = std::min(
             ModuleCounters[i].Start[j], UnstableCounters[UnstableIdx].Counter);
     }
   });
+  return Updated;
 }
 
-// Moves the minimum hit counts to ModuleCounters.
-void TracePC::ApplyUnstableCounters() {
+// Updates and applies unstable counters to ModuleCounters in single iteration
+void TracePC::UpdateAndApplyUnstableCounters(int UnstableMode) {
   IterateInline8bitCounters([&](int i, int j, int UnstableIdx) {
-    ModuleCounters[i].Start[j] = UnstableCounters[UnstableIdx].Counter;
+    if (ModuleCounters[i].Start[j] != UnstableCounters[UnstableIdx].Counter) {
+      UnstableCounters[UnstableIdx].IsUnstable = true;
+      if (UnstableMode == ZeroUnstable)
+        ModuleCounters[i].Start[j] = 0;
+      else if (UnstableMode == MinUnstable)
+        ModuleCounters[i].Start[j] = std::min(
+            ModuleCounters[i].Start[j], UnstableCounters[UnstableIdx].Counter);
+    }
   });
 }
 
 void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) {
   if (Start == Stop) return;
   if (NumModulesWithInline8bitCounters &&
       ModuleCounters[NumModulesWithInline8bitCounters-1].Start == Start) return;
   assert(NumModulesWithInline8bitCounters <