[NFC] Move CombinationGenerator from Exegesis to ADT

[courbet]

llvm/include/llvm/ADT/CombinationGenerator.h

16–17

I'm not sure this is very relevant here.

53

[nit] this does not have the semantics of operator++. Rename this to next() ?

62

I think this would be better as operator*.

[lebedev.ri]

@courbet thank you for taking a look!
Address nits.

llvm/include/llvm/ADT/CombinationGenerator.h

16–17

I think this is useful for understanding of the algorithm.

llvm/include/llvm/ADT/CombinationGenerator.h

+//===-- llvm/ADT/CombinationGenerator.h ------------------------*- C++ -*--===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Combination generator.
+///
+/// Example: given input {{0, 1}, {2}, {3, 4}} it will produce the following
+/// combinations: {0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4}.
+///
+/// It is useful to think of input as vector-of-vectors, where the
+/// outer vector is the variable space, and inner vector is choice space.
+/// The number of choices for each variable can be different.
+///
+/// As for implementation, it is useful to think of this as a weird number,
+/// where each digit (==variable) may have different base (==number of choices).
+/// Thus modelling of 'produce next combination' is exactly analogous to the
+/// incrementing of an number - increment lowest digit (pick next choice for the
+/// variable), and if it wrapped to the beginning then increment next digit.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_COMBINATIONGENERATOR_H
+#define LLVM_ADT_COMBINATIONGENERATOR_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include <cassert>
+#include <cstring>
+
+namespace llvm {
+
+template <typename choice_type, typename choices_storage_type,
+          int variable_smallsize>
+class CombinationGenerator {
+  template <typename T> struct WrappingIterator {
+    using value_type = T;
+
+    const ArrayRef<value_type> Range;
+    typename decltype(Range)::const_iterator Position;
+
+    // Rewind the tape, placing the position to again point at the beginning.
+    void rewind() { Position = Range.begin(); }
+
+    // Advance position forward, possibly wrapping to the beginning.
+    // Returns whether the wrap happened.
+    bool advance() {
+      ++Position;
+      bool Wrapped = Position == Range.end();
+      if (Wrapped)
+        rewind();
+      return Wrapped;
+    }
+
+    // Get the value at which we are currently pointing.
+    const value_type &operator*() const { return *Position; }
+
+    WrappingIterator(ArrayRef<value_type> Range_) : Range(Range_) {
+      assert(!Range.empty() && "The range must not be empty.");
+      rewind();
+    }
+  };
+
+  const ArrayRef<choices_storage_type> VariablesChoices;
+
+  void performGeneration(
+      const function_ref<bool(ArrayRef<choice_type>)> Callback) const {
+    SmallVector<WrappingIterator<choice_type>, variable_smallsize>
+        VariablesState;
+
+    // 'increment' of the the whole VariablesState is defined identically to the
+    // increment of a number: starting from the least significant element,
+    // increment it, and if it wrapped, then propagate that carry by also
+    // incrementing next (more significant) element.
+    auto IncrementState =
+        [](MutableArrayRef<WrappingIterator<choice_type>> VariablesState)
+        -> bool {
+      for (WrappingIterator<choice_type> &Variable :
+           llvm::reverse(VariablesState)) {
+        bool Wrapped = Variable.advance();
+        if (!Wrapped)
+          return false; // There you go, next combination is ready.
+        // We have carry - increment more significant variable next..
+      }
+      return true; // MSB variable wrapped, no more unique combinations.
+    };
+
+    // Initialize the per-variable state to refer to the possible choices for
+    // that variable.
+    VariablesState.reserve(VariablesChoices.size());
+    for (ArrayRef<choice_type> VC : VariablesChoices)
+      VariablesState.emplace_back(VC);
+
+    // Temporary buffer to store each combination before performing Callback.
+    SmallVector<choice_type, variable_smallsize> CurrentCombination;
+    CurrentCombination.resize(VariablesState.size());
+
+    while (true) {
+      // Gather the currently-selected variable choices into a vector.
+      for (auto I : llvm::zip(VariablesState, CurrentCombination))
+        std::get<1>(I) = *std::get<0>(I);
+      // And pass the new combination into callback, as intended.
+      if (/*Abort=*/Callback(CurrentCombination))
+        return;
+      // And tick the state to next combination, which will be unique.
+      if (IncrementState(VariablesState))
+        return; // All combinations produced.
+    }
+  };
+
+public:
+  CombinationGenerator(ArrayRef<choices_storage_type> VariablesChoices_)
+      : VariablesChoices(VariablesChoices_) {
+#ifndef NDEBUG
+    assert(!VariablesChoices.empty() && "There should be some variables.");
+    llvm::for_each(VariablesChoices, [](ArrayRef<choice_type> VariableChoices) {
+      assert(!VariableChoices.empty() &&
+             "There must always be some choice, at least a placeholder one.");
+    });
+#endif
+  }
+
+  // How many combinations can we produce, max?
+  // This is at most how many times the callback will be called.
+  size_t numCombinations() const {
+    size_t NumVariants = 1;
+    for (ArrayRef<choice_type> VariableChoices : VariablesChoices)
+      NumVariants *= VariableChoices.size();
+    assert(NumVariants >= 1 &&
+           "We should always end up producing at least one combination");
+    return NumVariants;
+  }
+
+  // Actually perform exhaustive combination generation.
+  // Each result will be passed into the callback.
+  void generate(const function_ref<bool(ArrayRef<choice_type>)> Callback) {
+    performGeneration(Callback);
+  }
+};
+
+} // namespace llvm
+
+#endif

llvm/tools/llvm-exegesis/lib/SnippetGenerator.h

 #define LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H
 
 #include "Assembler.h"
 #include "BenchmarkCode.h"
 #include "CodeTemplate.h"
 #include "LlvmState.h"
 #include "MCInstrDescView.h"
 #include "RegisterAliasing.h"
+#include "llvm/ADT/CombinationGenerator.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/Error.h"
 #include <cstdlib>
 #include <memory>
 #include <vector>
 
 namespace llvm {
 namespace exegesis {
void setRandomAliasing(const AliasingConfigurations &AliasingConfigurations,
                        InstructionTemplate &DefIB, InstructionTemplate &UseIB);
 
 // Assigns a Random Value to all Variables in IT that are still Invalid.
 // Do not use any of the registers in `ForbiddenRegs`.
 Error randomizeUnsetVariables(const LLVMState &State,
                               const BitVector &ForbiddenRegs,
                               InstructionTemplate &IT);
 
-// Combination generator.
-//
-// Example: given input {{0, 1}, {2}, {3, 4}} it will produce the following
-// combinations: {0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4}.
-//
-// It is important to think of input as vector-of-vectors, where the
-// outer vector is the variable space, and inner vector is choice space.
-// The number of choices for each variable can be different.
-//
-// As for implementation, it is useful to think of this as a weird number,
-// where each digit (==variable) may have different base (==number of choices).
-// Thus modelling of 'produce next combination' is exactly analogous to the
-// incrementing of an number - increment lowest digit (pick next choice for the
-// variable), and if it wrapped to the beginning then increment next digit.
-template <typename choice_type, typename choices_storage_type,
-          int variable_smallsize>
-class CombinationGenerator {
-  template <typename T> struct WrappingIterator {
-    using value_type = T;
-
-    const ArrayRef<value_type> Range;
-    typename decltype(Range)::const_iterator Position;
-
-    // Rewind the tape, placing the position to again point at the beginning.
-    void rewind() { Position = Range.begin(); }
-
-    // Advance position forward, possibly wrapping to the beginning.
-    // Returns whether the wrap happened.
-    bool operator++() {
-      ++Position;
-      bool Wrapped = Position == Range.end();
-      if (Wrapped)
-        rewind();
-      return Wrapped;
-    }
-
-    // Get the value at which we are currently pointing.
-    operator const value_type &() const { return *Position; }
-
-    WrappingIterator(ArrayRef<value_type> Range_) : Range(Range_) {
-      assert(!Range.empty() && "The range must not be empty.");
-      rewind();
-    }
-  };
-
-  const ArrayRef<choices_storage_type> VariablesChoices;
-
-  void performGeneration(
-      const function_ref<bool(ArrayRef<choice_type>)> Callback) const {
-    SmallVector<WrappingIterator<choice_type>, variable_smallsize>
-        VariablesState;
-
-    // 'increment' of the the whole VariablesState is defined identically to the
-    // increment of a number: starting from the least significant element,
-    // increment it, and if it wrapped, then propagate that carry by also
-    // incrementing next (more significant) element.
-    auto IncrementState =
-        [](MutableArrayRef<WrappingIterator<choice_type>> VariablesState)
-        -> bool {
-      for (WrappingIterator<choice_type> &Variable :
-           llvm::reverse(VariablesState)) {
-        bool Wrapped = ++Variable;
-        if (!Wrapped)
-          return false; // There you go, next combination is ready.
-        // We have carry - increment more significant variable next..
-      }
-      return true; // MSB variable wrapped, no more unique combinations.
-    };
-
-    // Initialize the per-variable state to refer to the possible choices for
-    // that variable.
-    VariablesState.reserve(VariablesChoices.size());
-    for (ArrayRef<choice_type> VC : VariablesChoices)
-      VariablesState.emplace_back(VC);
-
-    // Temporary buffer to store each combination before performing Callback.
-    SmallVector<choice_type, variable_smallsize> CurrentCombination;
-    CurrentCombination.resize(VariablesState.size());
-
-    while (true) {
-      // Gather the currently-selected variable choices into a vector.
-      for (auto I : llvm::zip(VariablesState, CurrentCombination))
-        std::get<1>(I) = std::get<0>(I);
-      // And pass the new combination into callback, as intended.
-      if (/*Abort=*/Callback(CurrentCombination))
-        return;
-      // And tick the state to next combination, which will be unique.
-      if (IncrementState(VariablesState))
-        return; // All combinations produced.
-    }
-  };
-
-public:
-  CombinationGenerator(ArrayRef<choices_storage_type> VariablesChoices_)
-      : VariablesChoices(VariablesChoices_) {
-#ifndef NDEBUG
-    assert(!VariablesChoices.empty() && "There should be some variables.");
-    llvm::for_each(VariablesChoices, [](ArrayRef<choice_type> VariableChoices) {
-      assert(!VariableChoices.empty() &&
-             "There must always be some choice, at least a placeholder one.");
-    });
-#endif
-  }
-
-  // How many combinations can we produce, max?
-  // This is at most how many times the callback will be called.
-  size_t numCombinations() const {
-    size_t NumVariants = 1;
-    for (ArrayRef<choice_type> VariableChoices : VariablesChoices)
-      NumVariants *= VariableChoices.size();
-    assert(NumVariants >= 1 &&
-           "We should always end up producing at least one combination");
-    return NumVariants;
-  }
-
-  // Actually perform exhaustive combination generation.
-  // Each result will be passed into the callback.
-  void generate(const function_ref<bool(ArrayRef<choice_type>)> Callback) {
-    performGeneration(Callback);
-  }
-};
-
 } // namespace exegesis
 } // namespace llvm
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_SNIPPETGENERATOR_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   APSIntTest.cpp
   ArrayRefTest.cpp
   BitFieldsTest.cpp
   BitmaskEnumTest.cpp
   BitVectorTest.cpp
   BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
   CoalescingBitVectorTest.cpp
+  CombinationGeneratorTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   DirectedGraphTest.cpp
   EnumeratedArrayTest.cpp
   EquivalenceClassesTest.cpp

llvm/unittests/ADT/CombinationGeneratorTest.cpp

-//===-- SnippetGeneratorTest.cpp --------------------------------*- C++ -*-===//
+//===- llvm/unittest/ADT/CombinationGeneratorTest.cpp ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#include "SnippetGenerator.h"
+#include "llvm/ADT/CombinationGenerator.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/STLForwardCompat.h"
+#include "llvm/ADT/iterator_range.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
-#include <initializer_list>
+#include <algorithm>
+#include <cstddef>
+#include <iterator>
+#include <tuple>
+#include <vector>
 
-namespace llvm {
-namespace exegesis {
+using namespace llvm;
 
 namespace {
 
 TEST(CombinationGenerator, Square) {
   const std::vector<std::vector<int>> Choices{{0, 1}, {2, 3}};
 
   std::vector<std::vector<int>> Variants;
   CombinationGenerator<int, std::vector<int>, 4> G(Choices);
TEST(CombinationGenerator, Singleton) {
 
   const std::vector<std::vector<int>> ExpectedVariants{
       {0},
   };
   ASSERT_THAT(Variants, ::testing::SizeIs(NumVariants));
   ASSERT_THAT(Variants, ::testing::ContainerEq(ExpectedVariants));
 }
 
-} // namespace
-} // namespace exegesis
-} // namespace llvm
+} // end anonymous namespace

llvm/unittests/tools/llvm-exegesis/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   Symbolize
   )
 
 set(exegesis_sources
   BenchmarkRunnerTest.cpp
   ClusteringTest.cpp
   PerfHelperTest.cpp
   RegisterValueTest.cpp
-  SnippetGeneratorTest.cpp
   )
 
 set(exegesis_link_libraries LLVMExegesis)
 
 function(add_llvm_exegesis_unittest_includes)
   set(exegesis_includes ${exegesis_includes} ${ARGV} PARENT_SCOPE)
 endfunction()