[mlir][sparse] simplification of sparse runtime support lib

[aartbik]

Summary

Incorporated two header files directly into other since
other parts were used (and it makes it hard to find the
definitions). Removed TODOs that are less likely to be done.

mlir/include/mlir/ExecutionEngine/SparseTensor/ArithmeticUtils.h

 //===- ArithmeticUtils.h - Arithmetic helper functions ----------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
-// This header is not part of the public API.  It is placed in the
-// includes directory only because that's required by the implementations
-// of template-classes.
-//
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
+// A collection of "safe" arithmetic helper methods.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_ARITHMETICUTILS_H
 #define MLIR_EXECUTIONENGINE_SPARSETENSOR_ARITHMETICUTILS_H
 
-#include "mlir/ExecutionEngine/SparseTensor/Attributes.h"
-
 #include <cassert>
 #include <cinttypes>
 #include <limits>
 #include <type_traits>
 
 namespace mlir {
 namespace sparse_tensor {
 namespace detail {

 // functions only guarantee that *if* they return an answer then that answer
 // is correct.  When assertions are enabled, they do their best to remain
 // as fast as possible (since MLIR keeps assertions enabled by default,
 // even for optimized builds).  When assertions are disabled, they use the
 // standard unchecked implementations.
 //
 //===----------------------------------------------------------------------===//
 
-// TODO: we would like to be able to pass in custom error messages, to
-// improve the user experience.  We should be able to use something like
-// `assert(((void)(msg ? msg : defaultMsg), cond))`; but I'm not entirely
-// sure that'll work as intended when done within a function-definition
-// rather than within a macro-definition.
-
 /// A version of `static_cast<To>` which checks for overflow/underflow.
 /// The implementation avoids performing runtime assertions whenever
 /// the types alone are sufficient to statically prove that overflow
 /// cannot happen.
 template <typename To, typename From>
 [[nodiscard]] inline To checkOverflowCast(From x) {
   // Check the lower bound. (For when casting from signed types.)
   constexpr To minTo = std::numeric_limits<To>::min();
   constexpr From minFrom = std::numeric_limits<From>::min();
   if constexpr (!safelyGE(minFrom, minTo))
     assert(safelyGE(x, minTo) && "cast would underflow");
   // Check the upper bound.
   constexpr To maxTo = std::numeric_limits<To>::max();
   constexpr From maxFrom = std::numeric_limits<From>::max();
   if constexpr (!safelyLE(maxFrom, maxTo))
     assert(safelyLE(x, maxTo) && "cast would overflow");
   // Now do the cast itself.
   return static_cast<To>(x);
 }
 
 /// A version of `operator*` on `uint64_t` which guards against overflows
 /// (when assertions are enabled).
 inline uint64_t checkedMul(uint64_t lhs, uint64_t rhs) {
-  // If assertions are enabled and we have the intrinsic, then use it to
-  // avoid the expensive division.  If assertions are disabled, then don't
-  // bother with intrinsics (to avoid any possible slowdown vs `operator*`).
-#if !defined(NDEBUG) && MLIR_SPARSETENSOR_HAS_BUILTIN(__builtin_mul_overflow)
-  uint64_t result;
-  bool overflowed = __builtin_mul_overflow(lhs, rhs, &result);
-  assert(!overflowed && "Integer overflow");
-  return result;
-#else
   assert((lhs == 0 || rhs <= std::numeric_limits<uint64_t>::max() / lhs) &&
          "Integer overflow");
   return lhs * rhs;
-#endif
 }
 
 } // namespace detail
 } // namespace sparse_tensor
 } // namespace mlir
 
 #endif // MLIR_EXECUTIONENGINE_SPARSETENSOR_ARITHMETICUTILS_H

mlir/include/mlir/ExecutionEngine/SparseTensor/Attributes.h

-//===- Attributes.h - C++ attributes for SparseTensorRuntime ----*- 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
-//
-//===----------------------------------------------------------------------===//
-//
-// This header defines various macros for using C++ attributes whenever
-// they're supported by the compiler.  These macros are the same as the
-// versions in the LLVMSupport library, but we define our own versions
-// in order to avoid introducing that dependency just for the sake of
-// these macros.  (If we ever do end up depending on LLVMSupport, then
-// we should remove this header and use "llvm/Support/Compiler.h" instead.)
-//
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_ATTRIBUTES_H
-#define MLIR_EXECUTIONENGINE_SPARSETENSOR_ATTRIBUTES_H
-
-// A wrapper around `__has_cpp_attribute` for C++11 style attributes,
-// which are defined by ISO C++ SD-6.
-// <https://en.cppreference.com/w/cpp/experimental/feature_test>
-#if defined(__cplusplus) && defined(__has_cpp_attribute)
-// NOTE: The __cplusplus requirement should be unnecessary, but guards
-// against issues with GCC <https://bugs.llvm.org/show_bug.cgi?id=23435>.
-#define MLIR_SPARSETENSOR_HAS_CPP_ATTRIBUTE(x) __has_cpp_attribute(x)
-#else
-#define MLIR_SPARSETENSOR_HAS_CPP_ATTRIBUTE(x) 0
-#endif
-
-// A wrapper around `__has_attribute`, which is defined by GCC 5+ and Clang.
-// GCC: <https://gcc.gnu.org/gcc-5/changes.html>
-// Clang: <https://clang.llvm.org/docs/LanguageExtensions.html>
-#ifdef __has_attribute
-#define MLIR_SPARSETENSOR_HAS_ATTRIBUTE(x) __has_attribute(x)
-#else
-#define MLIR_SPARSETENSOR_HAS_ATTRIBUTE(x) 0
-#endif
-
-// A wrapper around `__has_builtin`, which is defined by GCC and Clang
-// but is missing on some versions of MSVC.
-// GCC: <https://gcc.gnu.org/onlinedocs/cpp/_005f_005fhas_005fbuiltin.html>
-// Clang: <https://clang.llvm.org/docs/LanguageExtensions.html#has-builtin>
-#ifdef __has_builtin
-#define MLIR_SPARSETENSOR_HAS_BUILTIN(x) __has_builtin(x)
-#else
-#define MLIR_SPARSETENSOR_HAS_BUILTIN(x) 0
-#endif
-
-// An attribute for non-owning classes (like `PermutationRef`) to enable
-// lifetime warnings.
-#if MLIR_SPARSETENSOR_HAS_CPP_ATTRIBUTE(gsl::Pointer)
-#define MLIR_SPARSETENSOR_GSL_POINTER [[gsl::Pointer]]
-#else
-#define MLIR_SPARSETENSOR_GSL_POINTER
-#endif
-
-// An attribute for functions which are "pure" in the following sense:
-// * the result depends only on the function arguments
-// * pointer arguments are allowed to be read from, but not written to
-// * has no observable effects other than the return value
-//
-// This allows the compiler to avoid repeated function calls whenever
-// it can determine that the arguments are the same and that memory has
-// not changed.
-//
-// This macro is called `LLVM_READONLY` by LLVMSupport.  This definition
-// differs slightly from the LLVM version by using `gnu::pure` when
-// available, like Abseil's `ABSL_ATTRIBUTE_PURE_FUNCTION`.
-#if MLIR_SPARSETENSOR_HAS_CPP_ATTRIBUTE(gnu::pure)
-#define MLIR_SPARSETENSOR_PURE [[gnu::pure]]
-#elif MLIR_SPARSETENSOR_HAS_ATTRIBUTE(pure) || defined(__GNUC__)
-#define MLIR_SPARSETENSOR_PURE __attribute__((pure))
-#else
-#define MLIR_SPARSETENSOR_PURE
-#endif
-
-#endif // MLIR_EXECUTIONENGINE_SPARSETENSOR_ATTRIBUTES_H

mlir/include/mlir/ExecutionEngine/SparseTensor/COO.h

 //===- COO.h - Coordinate-scheme sparse tensor representation ---*- 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
 //
 //===----------------------------------------------------------------------===//
 //
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
+// This file contains a coordinate-scheme representation of sparse tensors.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_COO_H
 #define MLIR_EXECUTIONENGINE_SPARSETENSOR_COO_H
 
 #include <algorithm>
 #include <cassert>

 using ElementConsumer =
     const std::function<void(const std::vector<uint64_t> &, V)> &;
 
 /// A memory-resident sparse tensor in coordinate-scheme representation
 /// (a collection of `Element`s).  This data structure is used as
 /// an intermediate representation; e.g., for reading sparse tensors
 /// from external formats into memory, or for certain conversions between
 /// different `SparseTensorStorage` formats.
-///
-/// This class provides all the typedefs required by the "Container"
-/// concept (<https://en.cppreference.com/w/cpp/named_req/Container>);
-/// however, beware that it cannot fully implement that concept since
-/// it cannot have a default ctor (because the `dimSizes` field is const).
-/// Thus these typedefs are provided for familiarity reasons, rather
-/// than as a proper implementation of the concept.
 template <typename V>
 class SparseTensorCOO final {
 public:
   using value_type = const Element<V>;
   using reference = value_type &;
   using const_reference = reference;
-  // The types associated with `std::vector` differ significantly between
-  // C++11/17 vs C++20; so we explicitly defer to whatever `std::vector`
-  // says the types should be.
   using vector_type = std::vector<Element<V>>;
   using iterator = typename vector_type::const_iterator;
   using const_iterator = iterator;
   using difference_type = typename vector_type::difference_type;
   using size_type = typename vector_type::size_type;
 
   /// Constructs a new coordinate-scheme sparse tensor with the given
   /// sizes and initial storage capacity.

mlir/include/mlir/ExecutionEngine/SparseTensor/ErrorHandling.h

 //===- ErrorHandling.h - Helpers for errors ---------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
-// This header is not part of the public API.  It is placed in the
-// includes directory only because that's required by the implementations
-// of template-classes.
-//
 // This file defines an extremely lightweight API for fatal errors (not
 // arising from assertions).  The API does not attempt to be sophisticated
 // in any way, it's just the usual "I give up" style of error reporting.
 //
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
-//
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_ERRORHANDLING_H
 #define MLIR_EXECUTIONENGINE_SPARSETENSOR_ERRORHANDLING_H
 
 #include <cstdio>
 #include <cstdlib>
 

mlir/include/mlir/ExecutionEngine/SparseTensor/File.h

 // following external formats:
 //
 // (1) Matrix Market Exchange (MME): *.mtx
 //     https://math.nist.gov/MatrixMarket/formats.html
 //
 // (2) Formidable Repository of Open Sparse Tensors and Tools (FROSTT): *.tns
 //     http://frostt.io/tensors/file-formats.html
 //
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
-//
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_FILE_H
 #define MLIR_EXECUTIONENGINE_SPARSETENSOR_FILE_H
 
-#include "mlir/ExecutionEngine/SparseTensor/PermutationRef.h"
 #include "mlir/ExecutionEngine/SparseTensor/Storage.h"
 
 #include <fstream>
 
 namespace mlir {
 namespace sparse_tensor {
 
 namespace detail {

 inline V readValue(char **linePtr, bool isPattern) {
   return isPattern ? readValue<V, true>(linePtr) : readValue<V, false>(linePtr);
 }
 
 } // namespace detail
 
 //===----------------------------------------------------------------------===//
 
-// TODO: benchmark whether to keep various methods inline vs moving them
-// off to the cpp file.
-
-// TODO: consider distinguishing separate classes for before vs
-// after reading the header; so as to statically avoid the need
-// to `assert(isValid())`.
-
 /// This class abstracts over the information stored in file headers,
 /// as well as providing the buffers and methods for parsing those headers.
 class SparseTensorReader final {
 public:
   enum class ValueKind : uint8_t {
     // The value before calling `readHeader`.
     kInvalid = 0,
     // Values that can be set by `readMMEHeader`.

mlir/include/mlir/ExecutionEngine/SparseTensor/PermutationRef.h

-//===- PermutationRef.h - Permutation reference wrapper ---------*- 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
-//
-//===----------------------------------------------------------------------===//
-//
-// This header is not part of the public API.  It is placed in the
-// includes directory only because that's required by the implementations
-// of template-classes.
-//
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_PERMUTATIONREF_H
-#define MLIR_EXECUTIONENGINE_SPARSETENSOR_PERMUTATIONREF_H
-
-#include "mlir/ExecutionEngine/SparseTensor/Attributes.h"
-#include "mlir/ExecutionEngine/SparseTensor/ErrorHandling.h"
-
-#include <cassert>
-#include <cinttypes>
-#include <vector>
-
-namespace mlir {
-namespace sparse_tensor {
-namespace detail {
-
-/// Checks whether the `perm` array is a permutation of `[0 .. size)`.
-MLIR_SPARSETENSOR_PURE bool isPermutation(uint64_t size, const uint64_t *perm);
-
-/// Wrapper around `isPermutation` to ensure consistent error messages.
-inline void assertIsPermutation(uint64_t size, const uint64_t *perm) {
-#ifndef NDEBUG
-  if (!isPermutation(size, perm))
-    MLIR_SPARSETENSOR_FATAL("Not a permutation of [0..%" PRIu64 ")\n", size);
-#endif
-}
-
-// TODO: To implement things like `inverse` and `compose` while preserving
-// the knowledge that `isPermutation` is true, we'll need to also have
-// an owning version of `PermutationRef`.  (Though ideally we'll really
-// want to defunctionalize those methods so that we can avoid intermediate
-// arrays/copies and only materialize the data on request.)
-
-/// A non-owning class for capturing the knowledge that `isPermutation`
-/// is true, to avoid needing to assert it repeatedly.
-class MLIR_SPARSETENSOR_GSL_POINTER [[nodiscard]] PermutationRef final {
-public:
-  /// Asserts `isPermutation` and returns the witness to that being true.
-  //
-  // TODO: For now the assertive ctor is sufficient, but in principle
-  // we'll want a factory that can optionally construct the object
-  // (so callers can handle errors themselves).
-  explicit PermutationRef(uint64_t size, const uint64_t *perm)
-      : permSize(size), perm(perm) {
-    assertIsPermutation(size, perm);
-  }
-
-  uint64_t size() const { return permSize; }
-
-  const uint64_t *data() const { return perm; }
-
-  const uint64_t &operator[](uint64_t i) const {
-    assert(i < permSize && "index is out of bounds");
-    return perm[i];
-  }
-
-  /// Constructs a pushforward array of values.  This method is the inverse
-  /// of `permute` in the sense that for all `p` and `xs` we have:
-  /// * `p.permute(p.pushforward(xs)) == xs`
-  /// * `p.pushforward(p.permute(xs)) == xs`
-  template <typename T>
-  inline std::vector<T> pushforward(const std::vector<T> &values) const {
-    return pushforward(values.size(), values.data());
-  }
-
-  template <typename T>
-  inline std::vector<T> pushforward(uint64_t size, const T *values) const {
-    std::vector<T> out(permSize);
-    pushforward(size, values, out.data());
-    return out;
-  }
-
-  // NOTE: This form of the method is required by `toMLIRSparseTensor`,
-  // so it can reuse the `out` buffer for each iteration of a loop.
-  template <typename T>
-  inline void pushforward(uint64_t size, const T *values, T *out) const {
-    assert(size == permSize && "size mismatch");
-    for (uint64_t i = 0; i < permSize; ++i)
-      out[perm[i]] = values[i];
-  }
-
-  // NOTE: this is only needed by `toMLIRSparseTensor`, which in
-  // turn only needs it as a vector to hand off to `newSparseTensor`.
-  // Otherwise we would want the result to be an owning-permutation,
-  // to retain the knowledge that `isPermutation` is true.
-  //
-  /// Constructs the inverse permutation.  This is equivalent to calling
-  /// `pushforward` with `std::iota` for the values.
-  std::vector<uint64_t> inverse() const;
-
-  /// Constructs a permuted array of values.  This method is the inverse
-  /// of `pushforward` in the sense that for all `p` and `xs` we have:
-  /// * `p.permute(p.pushforward(xs)) == xs`
-  /// * `p.pushforward(p.permute(xs)) == xs`
-  template <typename T>
-  inline std::vector<T> permute(const std::vector<T> &values) const {
-    return permute(values.size(), values.data());
-  }
-
-  template <typename T>
-  inline std::vector<T> permute(uint64_t size, const T *values) const {
-    std::vector<T> out(permSize);
-    permute(size, values, out.data());
-    return out;
-  }
-
-  template <typename T>
-  inline void permute(uint64_t size, const T *values, T *out) const {
-    assert(size == permSize && "size mismatch");
-    for (uint64_t i = 0; i < permSize; ++i)
-      out[i] = values[perm[i]];
-  }
-
-private:
-  const uint64_t permSize;
-  const uint64_t *const perm; // non-owning pointer.
-};
-
-} // namespace detail
-} // namespace sparse_tensor
-} // namespace mlir
-
-#endif // MLIR_EXECUTIONENGINE_SPARSETENSOR_PERMUTATIONREF_H

mlir/include/mlir/ExecutionEngine/SparseTensor/Storage.h

 //===- Storage.h - TACO-flavored sparse tensor representation ---*- 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
 //
 //===----------------------------------------------------------------------===//
 //
-// This file is part of the lightweight runtime support library for sparse
-// tensor manipulations.  The functionality of the support library is meant
-// to simplify benchmarking, testing, and debugging MLIR code operating on
-// sparse tensors.  However, the provided functionality is **not** part of
-// core MLIR itself.
-//
 // This file contains definitions for the following classes:
 //
 // * `SparseTensorStorageBase`
 // * `SparseTensorStorage<P, C, V>`
 // * `SparseTensorEnumeratorBase<V>`
 // * `SparseTensorEnumerator<P, C, V>`
 // * `SparseTensorNNZ`
 //
-// Ideally we would split the storage classes and enumerator classes
-// into separate files, to improve legibility.  But alas: because these
-// are template-classes, they must therefore provide *definitions* in the
-// header; and those definitions cause circular dependencies that make it
-// impossible to split the file up along the desired lines.  (We could
-// split the base classes from the derived classes, but that doesn't
-// particularly help improve legibility.)
-//
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_EXECUTIONENGINE_SPARSETENSOR_STORAGE_H
 #define MLIR_EXECUTIONENGINE_SPARSETENSOR_STORAGE_H
 
 #include "mlir/Dialect/SparseTensor/IR/Enums.h"
 #include "mlir/ExecutionEngine/Float16bits.h"
 #include "mlir/ExecutionEngine/SparseTensor/ArithmeticUtils.h"
-#include "mlir/ExecutionEngine/SparseTensor/Attributes.h"
 #include "mlir/ExecutionEngine/SparseTensor/COO.h"
 #include "mlir/ExecutionEngine/SparseTensor/ErrorHandling.h"
 
 namespace mlir {
 namespace sparse_tensor {
 
+namespace detail {
+
+/// Checks whether the `perm` array is a permutation of `[0 .. size)`.
+inline bool isPermutation(uint64_t size, const uint64_t *perm) {
+  assert(perm && "Got nullptr for permutation");
+  std::vector<bool> seen(size, false);
+  for (uint64_t i = 0; i < size; ++i) {
+    const uint64_t j = perm[i];
+    if (j >= size || seen[j])
+      return false;
+    seen[j] = true;
+  }
+  for (uint64_t i = 0; i < size; ++i)
+    if (!seen[i])
+      return false;
+  return true;
+}
+
+/// Wrapper around `isPermutation` to ensure consistent error messages.
+inline void assertIsPermutation(uint64_t size, const uint64_t *perm) {
+#ifndef NDEBUG
+  if (!isPermutation(size, perm))
+    MLIR_SPARSETENSOR_FATAL("Not a permutation of [0..%" PRIu64 ")\n", size);
+#endif
+}
+
+/// A class for capturing the knowledge that `isPermutation` is true.
+class PermutationRef final {
+public:
+  /// Asserts `isPermutation` and returns the witness to that being true.
+  explicit PermutationRef(uint64_t size, const uint64_t *perm)
+      : permSize(size), perm(perm) {
+    assertIsPermutation(size, perm);
+  }
+
+  uint64_t size() const { return permSize; }
+
+  const uint64_t *data() const { return perm; }
+
+  const uint64_t &operator[](uint64_t i) const {
+    assert(i < permSize && "index is out of bounds");
+    return perm[i];
+  }
+
+  /// Constructs a pushforward array of values.  This method is the inverse
+  /// of `permute` in the sense that for all `p` and `xs` we have:
+  /// * `p.permute(p.pushforward(xs)) == xs`
+  /// * `p.pushforward(p.permute(xs)) == xs`
+  template <typename T>
+  inline std::vector<T> pushforward(const std::vector<T> &values) const {
+    return pushforward(values.size(), values.data());
+  }
+
+  template <typename T>
+  inline std::vector<T> pushforward(uint64_t size, const T *values) const {
+    std::vector<T> out(permSize);
+    pushforward(size, values, out.data());
+    return out;
+  }
+
+  // NOTE: This form of the method is required by `toMLIRSparseTensor`,
+  // so it can reuse the `out` buffer for each iteration of a loop.
+  template <typename T>
+  inline void pushforward(uint64_t size, const T *values, T *out) const {
+    assert(size == permSize && "size mismatch");
+    for (uint64_t i = 0; i < permSize; ++i)
+      out[perm[i]] = values[i];
+  }
+
+  // NOTE: this is only needed by `toMLIRSparseTensor`, which in
+  // turn only needs it as a vector to hand off to `newSparseTensor`.
+  // Otherwise we would want the result to be an owning-permutation,
+  // to retain the knowledge that `isPermutation` is true.
+  //
+  /// Constructs the inverse permutation.  This is equivalent to calling
+  /// `pushforward` with `std::iota` for the values.
+  inline std::vector<uint64_t> inverse() const {
+    std::vector<uint64_t> out(permSize);
+    for (uint64_t i = 0; i < permSize; ++i)
+      out[perm[i]] = i;
+    return out;
+  }
+
+  /// Constructs a permuted array of values.  This method is the inverse
+  /// of `pushforward` in the sense that for all `p` and `xs` we have:
+  /// * `p.permute(p.pushforward(xs)) == xs`
+  /// * `p.pushforward(p.permute(xs)) == xs`
+  template <typename T>
+  inline std::vector<T> permute(const std::vector<T> &values) const {
+    return permute(values.size(), values.data());
+  }
+
+  template <typename T>
+  inline std::vector<T> permute(uint64_t size, const T *values) const {
+    std::vector<T> out(permSize);
+    permute(size, values, out.data());
+    return out;
+  }
+
+  template <typename T>
+  inline void permute(uint64_t size, const T *values, T *out) const {
+    assert(size == permSize && "size mismatch");
+    for (uint64_t i = 0; i < permSize; ++i)
+      out[i] = values[perm[i]];
+  }
+
+private:
+  const uint64_t permSize;
+  const uint64_t *const perm; // non-owning pointer.
+};
+
+} // namespace detail
+
 //===----------------------------------------------------------------------===//
 // This forward decl is sufficient to split `SparseTensorStorageBase` into
 // its own header, but isn't sufficient for `SparseTensorStorage` to join it.
 template <typename V>
 class SparseTensorEnumeratorBase;
 
 // These macros ensure consistent error messages, without risk of incuring
 // an additional method call to do so.

 
 private:
   /// Appends an arbitrary new position to `positions[lvl]`.  This method
   /// checks that `pos` is representable in the `P` type; however, it
   /// does not check that `pos` is semantically valid (i.e., larger than
   /// the previous position and smaller than `coordinates[lvl].capacity()`).
   void appendPos(uint64_t lvl, uint64_t pos, uint64_t count = 1) {
     ASSERT_COMPRESSED_LVL(lvl);
-    // TODO: we'd like to recover the nicer error message:
-    // "Position value is too large for the P-type"
     positions[lvl].insert(positions[lvl].end(), count,
                           detail::checkOverflowCast<P>(pos));
   }
 
   /// Appends coordinate `crd` to level `lvl`, in the semantically
   /// general sense.  For non-dense levels, that means appending to the
   /// `coordinates[lvl]` array, checking that `crd` is representable in
   /// the `C` type; however, we do not verify other semantic requirements
   /// (e.g., that `crd` is in bounds for `lvlSizes[lvl]`, and not previously
   /// occurring in the same segment).  For dense levels, this method instead
   /// appends the appropriate number of zeros to the `values` array, where
   /// `full` is the number of "entries" already written to `values` for this
   /// segment (aka one after the highest coordinate previously appended).
   void appendCrd(uint64_t lvl, uint64_t full, uint64_t crd) {
     const auto dlt = getLvlType(lvl); // Avoid redundant bounds checking.
     if (isCompressedDLT(dlt) || isSingletonDLT(dlt)) {
-      // TODO: we'd like to recover the nicer error message:
-      // "Coordinate value is too large for the C-type"
       coordinates[lvl].push_back(detail::checkOverflowCast<C>(crd));
     } else { // Dense level.
       ASSERT_DENSE_DLT(dlt);
       assert(crd >= full && "Coordinate was already filled");
       if (crd == full)
         return; // Short-circuit, since it'll be a nop.
       if (lvl + 1 == getLvlRank())
         values.insert(values.end(), crd - full, 0);
       else
         finalizeSegment(lvl + 1, 0, crd - full);
     }
   }
 
   /// Writes the given coordinate to `coordinates[lvl][pos]`.  This method
   /// checks that `crd` is representable in the `C` type; however, it
   /// does not check that `crd` is semantically valid (i.e., in bounds
   /// for `dimSizes[lvl]` and not elsewhere occurring in the same segment).
   void writeCrd(uint64_t lvl, uint64_t pos, uint64_t crd) {
     ASSERT_COMPRESSED_OR_SINGLETON_LVL(lvl);
     // Subscript assignment to `std::vector` requires that the `pos`-th
     // entry has been initialized; thus we must be sure to check `size()`
     // here, instead of `capacity()` as would be ideal.
     assert(pos < coordinates[lvl].size() && "Position is out of bounds");
-    // TODO: we'd like to recover the nicer error message:
-    // "Coordinate value is too large for the C-type"
     coordinates[lvl][pos] = detail::checkOverflowCast<C>(crd);
   }
 
   /// Computes the assembled-size associated with the `l`-th level,
   /// given the assembled-size associated with the `(l-1)`-th level.
   /// "Assembled-sizes" correspond to the (nominal) sizes of overhead
   /// storage, as opposed to "level-sizes" which are the cardinality
   /// of possible coordinates for that level.

 /// Design Note: The reason we define this class instead of simply using
 /// `SparseTensorEnumerator<P,C,V>` is because we need to hide/generalize
 /// the `<P,C>` template parameters from MLIR client code (to simplify the
 /// type parameters used for direct sparse-to-sparse conversion).  And the
 /// reason we define the `SparseTensorEnumerator<P,C,V>` subclasses rather
 /// than simply using this class, is to avoid the cost of virtual-method
 /// dispatch within the loop-nest.
 template <typename V>
-class MLIR_SPARSETENSOR_GSL_POINTER [[nodiscard]] SparseTensorEnumeratorBase {
+class SparseTensorEnumeratorBase {
 public:
   /// Constructs an enumerator which automatically applies the given
   /// mapping from the source tensor's dimensions to the desired
   /// target tensor dimensions.
   ///
   /// Preconditions:
   /// * the `src` must have the same `V` value type.
   /// * `trgSizes` must be valid for `trgRank`.
protected:
   const SparseTensorStorageBase &src;
   std::vector<uint64_t> trgSizes;  // in target order.
   std::vector<uint64_t> lvl2trg;   // source-levels -> target-dims/lvls.
   std::vector<uint64_t> trgCursor; // in target order.
 };
 
 //===----------------------------------------------------------------------===//
 template <typename P, typename C, typename V>
-class MLIR_SPARSETENSOR_GSL_POINTER [[nodiscard]] SparseTensorEnumerator final
+class SparseTensorEnumerator final
     : public SparseTensorEnumeratorBase<V> {
   using Base = SparseTensorEnumeratorBase<V>;
   using StorageImpl = SparseTensorStorage<P, C, V>;
 
 public:
   /// Constructs an enumerator which automatically applies the given
   /// mapping from the source tensor's dimensions to the desired
   /// target tensor dimensions.

 ///
 /// N.B., this class stores references to the parameters passed to
 /// the constructor; thus, objects of this class must not outlive
 /// those parameters.
 ///
 /// This class does not have the "dimension" vs "level" distinction, but
 /// since it is used for initializing the levels of a `SparseTensorStorage`
 /// object, we use the "level" name throughout for the sake of consistency.
-class MLIR_SPARSETENSOR_GSL_POINTER [[nodiscard]] SparseTensorNNZ final {
+class SparseTensorNNZ final {
 public:
   /// Allocates the statistics structure for the desired target-tensor
   /// level structure (i.e., sizes and types).  This constructor does not
   /// actually populate the statistics, however; for that see `initialize`.
   ///
   /// Precondition: `lvlSizes` must not contain zeros.
   /// Asserts: `lvlSizes.size() == lvlTypes.size()`.
   SparseTensorNNZ(const std::vector<uint64_t> &lvlSizes,

mlir/lib/ExecutionEngine/SparseTensor/CMakeLists.txt

 # Unlike mlir_float16_utils, mlir_c_runner_utils, etc, we do *not* make
 # this a shared library: because doing so causes issues when building
 # on Windows.  In particular, various functions take/return `std::vector`
 # but that class is not designed with dllimport/dllexport pragma,
 # therefore it cannot be safely/correctly used across DLL boundaries.
 # Consequently, we avoid using the "mlir_xxx_utils" naming scheme, since
 # that is reserved/intended for shared libraries only.
 add_mlir_library(MLIRSparseTensorRuntime
   File.cpp
   NNZ.cpp
-  PermutationRef.cpp
   Storage.cpp
 
   EXCLUDE_FROM_LIBMLIR
 
   LINK_LIBS PUBLIC
   MLIRSparseTensorEnums
   mlir_float16_utils
   )
 set_property(TARGET MLIRSparseTensorRuntime PROPERTY CXX_STANDARD 17)
 
-# To make sure we adhere to the style guide:
-# <https://llvm.org/docs/CodingStandards.html#provide-a-virtual-method-anchor-for-classes-in-headers>
 check_cxx_compiler_flag(-Wweak-vtables
   COMPILER_SUPPORTS_WARNING_WEAK_VTABLES)
 if(COMPILER_SUPPORTS_WARNING_WEAK_VTABLES)
   target_compile_options(MLIRSparseTensorRuntime PUBLIC
     "-Wweak-vtables")
 endif()

mlir/lib/ExecutionEngine/SparseTensor/PermutationRef.cpp

-//===- PermutationRef.cpp - Permutation reference wrapper -----------------===//
-//
-// 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 "mlir/ExecutionEngine/SparseTensor/PermutationRef.h"
-
-#include <cassert>
-#include <cinttypes>
-#include <vector>
-
-bool mlir::sparse_tensor::detail::isPermutation(uint64_t size,
-                                                const uint64_t *perm) {
-  assert(perm && "Got nullptr for permutation");
-  // TODO: If we ever depend on LLVMSupport, then use `llvm::BitVector` instead.
-  std::vector<bool> seen(size, false);
-  for (uint64_t i = 0; i < size; ++i) {
-    const uint64_t j = perm[i];
-    if (j >= size || seen[j])
-      return false;
-    seen[j] = true;
-  }
-  for (uint64_t i = 0; i < size; ++i)
-    if (!seen[i])
-      return false;
-  return true;
-}
-
-std::vector<uint64_t>
-mlir::sparse_tensor::detail::PermutationRef::inverse() const {
-  std::vector<uint64_t> out(permSize);
-  for (uint64_t i = 0; i < permSize; ++i)
-    out[perm[i]] = i;
-  return out;
-}

mlir/lib/ExecutionEngine/SparseTensorRuntime.cpp

 #include "mlir/ExecutionEngine/SparseTensorRuntime.h"
 
 #ifdef MLIR_CRUNNERUTILS_DEFINE_FUNCTIONS
 
 #include "mlir/ExecutionEngine/SparseTensor/ArithmeticUtils.h"
 #include "mlir/ExecutionEngine/SparseTensor/COO.h"
 #include "mlir/ExecutionEngine/SparseTensor/ErrorHandling.h"
 #include "mlir/ExecutionEngine/SparseTensor/File.h"
-#include "mlir/ExecutionEngine/SparseTensor/PermutationRef.h"
 #include "mlir/ExecutionEngine/SparseTensor/Storage.h"
 
 #include <cstring>
 #include <numeric>
 
 using namespace mlir::sparse_tensor;
 
 //===----------------------------------------------------------------------===//

utils/bazel/llvm-project-overlay/mlir/BUILD.bazel

 # pragma, therefore it cannot be safely/correctly used across DLL boundaries.
 # Consequently, we avoid using the "mlir_xxx_utils" naming scheme,
 # since that is reserved/intended for shared libraries only.
 cc_library(
     name = "SparseTensorRuntime",
     srcs = [
         "lib/ExecutionEngine/SparseTensor/File.cpp",
         "lib/ExecutionEngine/SparseTensor/NNZ.cpp",
-        "lib/ExecutionEngine/SparseTensor/PermutationRef.cpp",
         "lib/ExecutionEngine/SparseTensor/Storage.cpp",
     ],
     hdrs = [
         "include/mlir/ExecutionEngine/SparseTensor/ArithmeticUtils.h",
-        "include/mlir/ExecutionEngine/SparseTensor/Attributes.h",
         "include/mlir/ExecutionEngine/SparseTensor/COO.h",
         "include/mlir/ExecutionEngine/SparseTensor/ErrorHandling.h",
         "include/mlir/ExecutionEngine/SparseTensor/File.h",
-        "include/mlir/ExecutionEngine/SparseTensor/PermutationRef.h",
         "include/mlir/ExecutionEngine/SparseTensor/Storage.h",
     ],
     includes = ["include"],
     deps = [
         ":SparseTensorEnums",
         ":mlir_float16_utils",
     ],
 )