[NFCI][llvm-reduce] Cleanup Delta passes to use Oracle abstraction

[lebedev.ri]

Summary

I think, this results in much more understandable/readable flow.
At least the original logic was perhaps the most hard thing for me to grasp when taking an initial look on the delta passes.

[nickdesaulniers]

Thanks, this makes the delta passes much more readable. It even looks like it might be simpler to avoid some of the local std::vector's now, folding some of the loops.

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

53

class

63

explicit

[lebedev.ri]

@nickdesaulniers thank you for taking a look!
Addressed review comments.

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

 // into chunks and tries to reduce the number chunks that are interesting.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
 #define LLVM_TOOLS_LLVMREDUCE_LLVMREDUCE_DELTA_H
 
 #include "TestRunner.h"
-#include <vector>
-#include <utility>
+#include "llvm/ADT/ScopeExit.h"
 #include <functional>
+#include <utility>
+#include <vector>
 
 namespace llvm {
 
 struct Chunk {
   int begin;
   int end;
 
   /// Helper function to verify if a given Target-index is inside the Chunk
struct Chunk {
   }
 
   /// Operator used for sets
   friend bool operator<(const Chunk &C1, const Chunk &C2) {
     return std::tie(C1.begin, C1.end) < std::tie(C2.begin, C2.end);
   }
 };
 
+/// Provides opaque interface for querying into ChunksToKeep without having to
+/// actually understand what is going on.
+class Oracle {
+  /// Out of all the features that we promised to be,
+  /// how many have we already processed? 1-based!
+  int Index = 1;
+
+  /// The actual workhorse, contains the knowledge whether or not
+  /// some particular feature should be preserved this time.
+  ArrayRef<Chunk> ChunksToKeep;
+
+public:
+  explicit Oracle(ArrayRef<Chunk> ChunksToKeep_)
+      : ChunksToKeep(ChunksToKeep_) {}
+
+  /// Should be called for each feature on which we are operating.
+  /// Name is self-explanatory - if returns true, then it should be preserved.
+  bool shouldKeep() {
+    if (ChunksToKeep.empty())
+      return false; // All further features are to be discarded.
+
+    // Does the current (front) chunk contain such a feature?
+    bool ShouldKeep = ChunksToKeep.front().contains(Index);
+    auto _ = make_scope_exit([&]() { ++Index; }); // Next time - next feature.
+
+    // Is this the last feature in the chunk?
+    if (ChunksToKeep.front().end == Index)
+      ChunksToKeep = ChunksToKeep.drop_front(); // Onto next chunk.
+
+    return ShouldKeep;
+  }
+};
+
 /// This function implements the Delta Debugging algorithm, it receives a
 /// number of Targets (e.g. Functions, Instructions, Basic Blocks, etc.) and
 /// splits them in half; these chunks of targets are then tested while ignoring
 /// one chunk, if a chunk is proven to be uninteresting (i.e. fails the test)
 /// it is removed from consideration. The algorithm will attempt to split the
 /// Chunks in half and start the process again until it can't split chunks
 /// anymore.
 ///

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

if (auto *CI = dyn_cast<CallInst>(*I++)) {
       ReplaceInstWithInst(CI, NewCI);
     }
 }
 
 /// Removes out-of-chunk arguments from functions, and modifies their calls
 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractArgumentsFromModule(std::vector<Chunk> ChunksToKeep,
                                        Module *Program) {
-  int I = 0, ArgCount = 0;
+  Oracle O(ChunksToKeep);
+
   std::set<Argument *> ArgsToKeep;
   std::vector<Function *> Funcs;
   // Get inside-chunk arguments, as well as their parent function
   for (auto &F : *Program)
     if (!F.isDeclaration()) {
       Funcs.push_back(&F);
       for (auto &A : F.args())
-        if (I < (int)ChunksToKeep.size()) {
-          if (ChunksToKeep[I].contains(++ArgCount))
-            ArgsToKeep.insert(&A);
-          if (ChunksToKeep[I].end == ArgCount)
-            ++I;
-        }
+        if (O.shouldKeep())
     }
 
   for (auto *F : Funcs) {
     ValueToValueMapTy VMap;
     std::vector<WeakVH> InstToDelete;
     for (auto &A : F->args())
       if (!ArgsToKeep.count(&A)) {
         // By adding undesired arguments to the VMap, CloneFunction will remove

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

for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
       }
     }
 }
 
 /// Removes out-of-chunk arguments from functions, and modifies their calls
 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractBasicBlocksFromModule(std::vector<Chunk> ChunksToKeep,
                                          Module *Program) {
-  int I = 0, BBCount = 0;
+  Oracle O(ChunksToKeep);
+
   std::set<BasicBlock *> BBsToKeep;
 
   for (auto &F : *Program)
     for (auto &BB : F)
-      if (I < (int)ChunksToKeep.size()) {
-        if (ChunksToKeep[I].contains(++BBCount))
-          BBsToKeep.insert(&BB);
-        if (ChunksToKeep[I].end == BBCount)
-          ++I;
-      }
+      if (O.shouldKeep())
 
   std::vector<BasicBlock *> BBsToDelete;
   for (auto &F : *Program)
     for (auto &BB : F) {
       if (!BBsToKeep.count(&BB)) {
         BBsToDelete.push_back(&BB);
         // Remove out-of-chunk BB from successor phi nodes
         for (auto *Succ : successors(&BB))

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

 #include <set>
 
 using namespace llvm;
 
 /// Removes all the Defined Functions (as well as their calls)
 /// that aren't inside any of the desired Chunks.
 static void extractFunctionsFromModule(const std::vector<Chunk> &ChunksToKeep,
                                        Module *Program) {
+  Oracle O(ChunksToKeep);
+
   // Get functions inside desired chunks
   std::set<Function *> FuncsToKeep;
-  int I = 0, FunctionCount = 0;
   for (auto &F : *Program)
-    if (I < (int)ChunksToKeep.size()) {
-      if (ChunksToKeep[I].contains(++FunctionCount))
-        FuncsToKeep.insert(&F);
-      if (FunctionCount == ChunksToKeep[I].end)
-        ++I;
-    }
+    if (O.shouldKeep())
 
   // Delete out-of-chunk functions, and replace their calls with undef
   std::vector<Function *> FuncsToRemove;
   SetVector<CallInst *> CallsToRemove;
   for (auto &F : *Program)
     if (!FuncsToKeep.count(&F)) {
       for (auto U : F.users())
         if (auto *Call = dyn_cast<CallInst>(U)) {

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

 #include "llvm/IR/Constants.h"
 #include <set>
 
 using namespace llvm;
 
 /// Removes all the Initialized GVs that aren't inside the desired Chunks.
 static void extractGVsFromModule(std::vector<Chunk> ChunksToKeep,
                                  Module *Program) {
+  Oracle O(ChunksToKeep);
+
   // Get GVs inside desired chunks
   std::set<GlobalVariable *> GVsToKeep;
-  int I = 0, GVCount = 0;
   for (auto &GV : Program->globals())
-    if (GV.hasInitializer() && I < (int)ChunksToKeep.size()) {
-      if (ChunksToKeep[I].contains(++GVCount))
-        GVsToKeep.insert(&GV);
-      if (GVCount == ChunksToKeep[I].end)
-        ++I;
-    }
+    if (GV.hasInitializer() && O.shouldKeep())
 
   // Delete out-of-chunk GVs and their uses
   std::vector<GlobalVariable *> ToRemove;
   std::vector<WeakVH> InstToRemove;
   for (auto &GV : Program->globals())
     if (GV.hasInitializer() && !GVsToKeep.count(&GV)) {
       for (auto U : GV.users())
         if (auto *Inst = dyn_cast<Instruction>(U))

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

 #include "ReduceInstructions.h"
 
 using namespace llvm;
 
 /// Removes out-of-chunk arguments from functions, and modifies their calls
 /// accordingly. It also removes allocations of out-of-chunk arguments.
 static void extractInstrFromModule(std::vector<Chunk> ChunksToKeep,
                                    Module *Program) {
-  int I = 0, InstCount = 0;
+  Oracle O(ChunksToKeep);
+
   std::set<Instruction *> InstToKeep;
 
   for (auto &F : *Program)
     for (auto &BB : F)
       for (auto &Inst : BB)
-        if (I < (int)ChunksToKeep.size()) {
-          if (ChunksToKeep[I].contains(++InstCount))
-            InstToKeep.insert(&Inst);
-          if (ChunksToKeep[I].end == InstCount)
-            ++I;
-        }
+        if (O.shouldKeep())
 
   std::vector<Instruction *> InstToDelete;
   for (auto &F : *Program)
     for (auto &BB : F)
       for (auto &Inst : BB)
         if (!InstToKeep.count(&Inst)) {
           Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
           InstToDelete.push_back(&Inst);

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

 #include "llvm/ADT/SmallVector.h"
 #include <set>
 #include <vector>
 
 using namespace llvm;
 
 /// Adds all Unnamed Metadata Nodes that are inside desired Chunks to set
 template <class T>
-static void getChunkMetadataNodes(T &MDUser, int &I,
-                                  const std::vector<Chunk> &ChunksToKeep,
+static void getChunkMetadataNodes(T &MDUser, Oracle &O,
                                   std::set<MDNode *> &SeenNodes,
                                   std::set<MDNode *> &NodesToKeep) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
   MDUser.getAllMetadata(MDs);
   for (auto &MD : MDs) {
     SeenNodes.insert(MD.second);
-    if (I < (int)ChunksToKeep.size()) {
-      if (ChunksToKeep[I].contains(SeenNodes.size()))
-        NodesToKeep.insert(MD.second);
-      if (ChunksToKeep[I].end == (int)SeenNodes.size())
-        ++I;
-    }
+    if (O.shouldKeep())
   }
 }
 
 /// Erases out-of-chunk unnamed metadata nodes from its user
 template <class T>
 static void eraseMetadataIfOutsideChunk(T &MDUser,
                                         const std::set<MDNode *> &NodesToKeep) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
   MDUser.getAllMetadata(MDs);
   for (int I = 0, E = MDs.size(); I != E; ++I)
     if (!NodesToKeep.count(MDs[I].second))
       MDUser.setMetadata(I, NULL);
 }
 
 /// Removes all the Named and Unnamed Metadata Nodes, as well as any debug
 /// functions that aren't inside the desired Chunks.
 static void extractMetadataFromModule(const std::vector<Chunk> &ChunksToKeep,
                                       Module *Program) {
+  Oracle O(ChunksToKeep);
+
   std::set<MDNode *> SeenNodes;
   std::set<MDNode *> NodesToKeep;
-  int I = 0;
 
   // Add chunk MDNodes used by GVs, Functions, and Instructions to set
   for (auto &GV : Program->globals())
-    getChunkMetadataNodes(GV, I, ChunksToKeep, SeenNodes, NodesToKeep);
+    getChunkMetadataNodes(GV, O, SeenNodes, NodesToKeep);
 
   for (auto &F : *Program) {
-    getChunkMetadataNodes(F, I, ChunksToKeep, SeenNodes, NodesToKeep);
+    getChunkMetadataNodes(F, O, SeenNodes, NodesToKeep);
     for (auto &BB : F)
       for (auto &Inst : BB)
-        getChunkMetadataNodes(Inst, I, ChunksToKeep, SeenNodes, NodesToKeep);
+        getChunkMetadataNodes(Inst, O, SeenNodes, NodesToKeep);
   }
 
   // Once more, go over metadata nodes, but deleting the ones outside chunks
   for (auto &GV : Program->globals())
     eraseMetadataIfOutsideChunk(GV, NodesToKeep);
 
   for (auto &F : *Program) {
     eraseMetadataIfOutsideChunk(F, NodesToKeep);
     for (auto &BB : F)
       for (auto &Inst : BB)
         eraseMetadataIfOutsideChunk(Inst, NodesToKeep);
   }
 
 
   // Get out-of-chunk Named metadata nodes
-  unsigned MetadataCount = SeenNodes.size();
   std::vector<NamedMDNode *> NamedNodesToDelete;
-  for (auto &MD : Program->named_metadata()) {
-    if (I < (int)ChunksToKeep.size()) {
-      if (!ChunksToKeep[I].contains(++MetadataCount))
-        NamedNodesToDelete.push_back(&MD);
-      if (ChunksToKeep[I].end == (int)SeenNodes.size())
-        ++I;
-    } else
-      NamedNodesToDelete.push_back(&MD);
-  }
+  for (auto &MD : Program->named_metadata())
+    if (!O.shouldKeep())
 
   for (auto *NN : NamedNodesToDelete) {
     for (int I = 0, E = NN->getNumOperands(); I != E; ++I)
       NN->setOperand(I, NULL);
     NN->eraseFromParent();
   }
 }
 

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

 //===----------------------------------------------------------------------===//
 
 #include "ReduceOperandBundles.h"
 #include "Delta.h"
 #include "TestRunner.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <iterator>
 #include <vector>
 
 namespace llvm {
 class Module;
 } // namespace llvm
 
 using namespace llvm;
 
 namespace {
 
-/// Provides opaque interface for querying into ChunksToKeep without having to
-/// actually understand what is going on.
-struct Oracle {
-  /// Out of all the features that we promised to be,
-  /// how many have we already processed? 1-based!
-  int Index = 1;
-
-  /// The actual workhorse, contains the knowledge whether or not
-  /// some particular feature should be preserved this time.
-  ArrayRef<Chunk> ChunksToKeep;
-
-public:
-  Oracle(ArrayRef<Chunk> ChunksToKeep_) : ChunksToKeep(ChunksToKeep_) {}
-
-  /// Should be called for each feature on which we are operating.
-  /// Name is self-explanatory - if returns true, then it should be preserved.
-  bool shouldKeep() {
-    if (ChunksToKeep.empty())
-      return false; // All further features are to be discarded.
-
-    // Does the current (front) chunk contain such a feature?
-    bool ShouldKeep = ChunksToKeep.front().contains(Index);
-    auto _ = make_scope_exit([&]() { ++Index; }); // Next time - next feature.
-
-    // Is this the last feature in the chunk?
-    if (ChunksToKeep.front().end == Index)
-      ChunksToKeep = ChunksToKeep.drop_front(); // Onto next chunk.
-
-    return ShouldKeep;
-  }
-};
-
 /// Given ChunksToKeep, produce a map of calls and indexes of operand bundles
 /// to be preserved for each call.
 class OperandBundleRemapper : public InstVisitor<OperandBundleRemapper> {
   Oracle O;
 
 public:
   DenseMap<CallBase *, std::vector<unsigned>> CallsToRefine;