[Reduce] Rewrite runDeltaPass() workloop: do reduce a single and/or last target

[lebedev.ri]

Summary

If there was a single target to begin with, because a single target
can only occupy a single chunk, we couldn't increase granularity.
and would immediately give up.

Likewise, if we had multiple targets, if by the end we'd end up with
a single target, we wouldn't finish reducing it, it would always
end up being "interesting"

[dblaikie]

Looks good - thanks!

[lebedev.ri]

In D84318#2167920, @dblaikie wrote:

Looks good - thanks!

Thank you for the review.

llvm/test/Reduce/remove-all-of-multiple-args.ll

 ; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
 
 define i32 @t(i32 %a0, i32 %a1, i32 %a2) {
 ; CHECK-ALL-LABEL: @t
-; CHECK-FINAL: (i32 %a0) {
+; CHECK-FINAL: () {
 ;
 ; CHECK-INTERESTINGNESS: ret i32
 ; CHECK-FINAL: ret i32 undef
 
   ret i32 %a1
 }

llvm/test/Reduce/remove-single-arg.ll

 ; RUN: llvm-reduce --test FileCheck --test-arg --check-prefixes=CHECK-ALL,CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
 ; RUN: cat %t | FileCheck --check-prefixes=CHECK-ALL,CHECK-FINAL %s
 
 define i32 @t(i32 %a0) {
 ; CHECK-ALL-LABEL: @t
-; CHECK-FINAL: (i32 %a0) {
+; CHECK-FINAL: () {
 ;
 ; CHECK-INTERESTINGNESS: ret i32
 ; CHECK-FINAL: ret i32 42
 
   ret i32 42
 }

llvm/tools/llvm-reduce/deltas/Delta.cpp

void llvm::runDeltaPass(
   if (Module *Program = Test.getProgram()) {
     SmallString<128> CurrentFilepath;
     if (!IsReduced(*Program, Test, CurrentFilepath)) {
       errs() << "\nInput isn't interesting! Verify interesting-ness test\n";
       exit(1);
     }
   }
 
-  std::vector<Chunk> Chunks = {{1, Targets}};
-  std::set<Chunk> UninterestingChunks;
+  std::vector<Chunk> ChunksStillConsideredInteresting = {{1, Targets}};
   std::unique_ptr<Module> ReducedProgram;
 
-  if (!increaseGranularity(Chunks)) {
-    errs() << "\nAlready at minimum size. Cannot reduce anymore.\n";
-    return;
-  }
-
+  bool FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity;
   do {
-    UninterestingChunks = {};
-    for (int I = Chunks.size() - 1; I >= 0; --I) {
-      std::vector<Chunk> CurrentChunks;
-
-      for (auto C : Chunks)
-        if (!UninterestingChunks.count(C) && C != Chunks[I])
-          CurrentChunks.push_back(C);
+    FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = false;
 
-      if (CurrentChunks.empty())
-        continue;
+    std::set<Chunk> UninterestingChunks;
+    for (Chunk &ChunkToCheckForUninterestingness :
+         reverse(ChunksStillConsideredInteresting)) {
+      // Take all of ChunksStillConsideredInteresting chunks, except those we've
+      // already deemed uninteresting (UninterestingChunks) but didn't remove
+      // from ChunksStillConsideredInteresting yet, and additionally ignore
+      // ChunkToCheckForUninterestingness chunk.
+      std::vector<Chunk> CurrentChunks;
+      CurrentChunks.reserve(ChunksStillConsideredInteresting.size() -
+                            UninterestingChunks.size() - 1);
+      copy_if(ChunksStillConsideredInteresting,
+              std::back_inserter(CurrentChunks), [&](const Chunk &C) {
+                return !UninterestingChunks.count(C) &&
+                       C != ChunkToCheckForUninterestingness;
+              });
 
       // Clone module before hacking it up..
       std::unique_ptr<Module> Clone = CloneModule(*Test.getProgram());
       // Generate Module with only Targets inside Current Chunks
       ExtractChunksFromModule(CurrentChunks, Clone.get());
 
       errs() << "Ignoring: ";
-      Chunks[I].print();
-      for (auto C : UninterestingChunks)
+      ChunkToCheckForUninterestingness.print();
+      for (const Chunk &C : UninterestingChunks)
         C.print();
 
-
-
       SmallString<128> CurrentFilepath;
       if (!IsReduced(*Clone, Test, CurrentFilepath)) {
+        // Program became non-reduced, so this chunk appears to be interesting.
         errs() << "\n";
         continue;
       }
 
-      UninterestingChunks.insert(Chunks[I]);
+      FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity = true;
+      UninterestingChunks.insert(ChunkToCheckForUninterestingness);
       ReducedProgram = std::move(Clone);
       errs() << " **** SUCCESS | lines: " << getLines(CurrentFilepath) << "\n";
     }
     // Delete uninteresting chunks
-    erase_if(Chunks, [&UninterestingChunks](const Chunk &C) {
+    erase_if(ChunksStillConsideredInteresting,
+             [&UninterestingChunks](const Chunk &C) {
                return UninterestingChunks.count(C);
              });
-
-  } while (!UninterestingChunks.empty() || increaseGranularity(Chunks));
+  } while (!ChunksStillConsideredInteresting.empty() &&
+           (FoundAtLeastOneNewUninterestingChunkWithCurrentGranularity ||
+            increaseGranularity(ChunksStillConsideredInteresting)));
 
   // If we reduced the testcase replace it
   if (ReducedProgram)
     Test.setProgram(std::move(ReducedProgram));
   errs() << "Couldn't increase anymore.\n";
 }