[mlir][sparse] Adding "final" keyword wherever appropriate

[wrengr]

Summary

This enables the compiler to perform devirtualization. And benchmarks
indicate devirtualization can sometimes give considerable speedup.

Depends On D122061

[aartbik]

Jumping a bit ahead in the stack, but this delta is good to go once base goes in as well.

[wrengr]

Rebasing for latest dependency (D122061 at diff 429856 2022-05-16T14:33)

mlir/lib/ExecutionEngine/SparseTensorUtils.cpp

 /// For example, a rank-1 vector element would look like
 ///   ({i}, a[i])
 /// and a rank-5 tensor element like
 ///   ({i,j,k,l,m}, a[i,j,k,l,m])
 /// We use pointer to a shared index pool rather than e.g. a direct
 /// vector since that (1) reduces the per-element memory footprint, and
 /// (2) centralizes the memory reservation and (re)allocation to one place.
 template <typename V>
-struct Element {
+struct Element final {
   Element(uint64_t *ind, V val) : indices(ind), value(val){};
   uint64_t *indices; // pointer into shared index pool
   V value;
 };
 
 /// The type of callback functions which receive an element.  We avoid
 /// packaging the coordinates and value together as an `Element` object
 /// because this helps keep code somewhat cleaner.
 template <typename V>
 using ElementConsumer =
     const std::function<void(const std::vector<uint64_t> &, V)> &;
 
 /// A memory-resident sparse tensor in coordinate scheme (collection of
 /// elements). This data structure is used to read a sparse tensor from
 /// any external format into memory and sort the elements lexicographically
 /// by indices before passing it back to the client (most packed storage
 /// formats require the elements to appear in lexicographic index order).
 template <typename V>
-struct SparseTensorCOO {
+struct SparseTensorCOO final {
 public:
   SparseTensorCOO(const std::vector<uint64_t> &szs, uint64_t capacity)
       : sizes(szs) {
     if (capacity) {
       elements.reserve(capacity);
       indices.reserve(capacity * getRank());
     }
   }

 
 /// A memory-resident sparse tensor using a storage scheme based on
 /// per-dimension sparse/dense annotations. This data structure provides a
 /// bufferized form of a sparse tensor type. In contrast to generating setup
 /// methods for each differently annotated sparse tensor, this method provides
 /// a convenient "one-size-fits-all" solution that simply takes an input tensor
 /// and annotations to implement all required setup in a general manner.
 template <typename P, typename I, typename V>
-class SparseTensorStorage : public SparseTensorStorageBase {
+class SparseTensorStorage final : public SparseTensorStorageBase {
   /// Private constructor to share code between the other constructors.
   /// Beware that the object is not necessarily guaranteed to be in a
   /// valid state after this constructor alone; e.g., `isCompressedDim(d)`
   /// doesn't entail `!(pointers[d].empty())`.
   ///
   /// Precondition: `perm` and `sparsity` must be valid for `szs.size()`.
   SparseTensorStorage(const std::vector<uint64_t> &szs, const uint64_t *perm,
                       const DimLevelType *sparsity)
public:
   ///
   /// Preconditions:
   /// * `perm` and `sparsity` must be valid for `szs.size()`.
   /// * The `tensor` must have the same value type `V`.
   SparseTensorStorage(const std::vector<uint64_t> &szs, const uint64_t *perm,
                       const DimLevelType *sparsity,
                       const SparseTensorStorageBase &tensor);
 
-  ~SparseTensorStorage() override = default;
+  ~SparseTensorStorage() final override = default;
 
   /// Partially specialize these getter methods based on template types.
-  void getPointers(std::vector<P> **out, uint64_t d) override {
+  void getPointers(std::vector<P> **out, uint64_t d) final override {
     assert(d < getRank());
     *out = &pointers[d];
   }
-  void getIndices(std::vector<I> **out, uint64_t d) override {
+  void getIndices(std::vector<I> **out, uint64_t d) final override {
     assert(d < getRank());
     *out = &indices[d];
   }
-  void getValues(std::vector<V> **out) override { *out = &values; }
+  void getValues(std::vector<V> **out) final override { *out = &values; }
 
   /// Partially specialize lexicographical insertions based on template types.
-  void lexInsert(const uint64_t *cursor, V val) override {
+  void lexInsert(const uint64_t *cursor, V val) final override {
     // First, wrap up pending insertion path.
     uint64_t diff = 0;
     uint64_t top = 0;
     if (!values.empty()) {
       diff = lexDiff(cursor);
       endPath(diff + 1);
       top = idx[diff] + 1;
     }
     // Then continue with insertion path.
     insPath(cursor, diff, top, val);
   }
 
   /// Partially specialize expanded insertions based on template types.
   /// Note that this method resets the values/filled-switch array back
   /// to all-zero/false while only iterating over the nonzero elements.
   void expInsert(uint64_t *cursor, V *values, bool *filled, uint64_t *added,
-                 uint64_t count) override {
+                 uint64_t count) final override {
     if (count == 0)
       return;
     // Sort.
     std::sort(added, added + count);
     // Restore insertion path for first insert.
     const uint64_t lastDim = getRank() - 1;
     uint64_t index = added[0];
     cursor[lastDim] = index;
for (uint64_t i = 1; i < count; i++) {
       insPath(cursor, lastDim, added[i - 1] + 1, values[index]);
       assert(filled[index]);
       values[index] = 0;
       filled[index] = false;
     }
   }
 
   /// Finalizes lexicographic insertions.
-  void endInsert() override {
+  void endInsert() final override {
     if (values.empty())
       finalizeSegment(0);
     else
       endPath(0);
   }
 
   void newEnumerator(SparseTensorEnumeratorBase<V> **out, uint64_t rank,
-                     const uint64_t *perm) const override {
+                     const uint64_t *perm) const final override {
     *out = new SparseTensorEnumerator<P, I, V>(*this, rank, perm);
   }
 
   /// Returns this sparse tensor storage scheme as a new memory-resident
   /// sparse tensor in coordinate scheme with the given dimension order.
   ///
   /// Precondition: `perm` must be valid for `getRank()`.
   SparseTensorCOO<V> *toCOO(const uint64_t *perm) const {

 
 /// Statistics regarding the number of nonzero subtensors in
 /// a source tensor, for direct sparse=>sparse conversion a la
 /// <https://arxiv.org/abs/2001.02609>.
 ///
 /// N.B., this class stores references to the parameters passed to
 /// the constructor; thus, objects of this class must not outlive
 /// those parameters.
-class SparseTensorNNZ {
+class SparseTensorNNZ final {
 public:
   /// Allocate the statistics structure for the desired sizes and
   /// sparsity (in the target tensor's storage-order).  This constructor
   /// does not actually populate the statistics, however; for that see
   /// `initialize`.
   ///
   /// Precondition: `szs` must not contain zeros.
   SparseTensorNNZ(const std::vector<uint64_t> &szs,