[mlir] Remove the use of FilterTypes for template metaprogramming

[rriddle]

Summary

This technique results in an explosion in compile time, resulting from a
huge number of std::tuple/concat instatiations. This technique is replaced
by simpler metaprogramming and results in a signficant reduction in
compile time. A local debug/asan build saw a 4x speed up in the processing
of ArithmeticOps.h.inc, and given the nature of this change every dialect
should see similar reductions in compile time.

[silvas]

Nice :)

[jpienaar]

In D123360#3439676, @silvas wrote:

Nice :)

Could you perhaps report the before and after on the case you mentioned was bad here to verify this fixes it? (seems likely but would be good to have verification)

[rriddle]

Tested on head and this sped up the compile time of InitAllDialects.h by slightly over 2x (in my debug/asan build), so committing. I'm going to try a few other tweaks to speed things up, but this is fairly significant.

mlir/include/mlir/IR/OpDefinition.h

 template <typename Trait>
 static std::enable_if_t<detect_has_fold_trait<Trait>::value, LogicalResult>
 foldTrait(Operation *op, ArrayRef<Attribute> operands,
           SmallVectorImpl<OpFoldResult> &results) {
   // If a previous trait has already been folded and replaced this operation, we
   // fail to fold this trait.
   return results.empty() ? Trait::foldTrait(op, operands, results) : failure();
 }
+template <typename Trait>
+static inline std::enable_if_t<!detect_has_any_fold_trait<Trait>::value,
+                               LogicalResult>
+foldTrait(Operation *, ArrayRef<Attribute>, SmallVectorImpl<OpFoldResult> &) {
+  return failure();
+}
 
-/// The internal implementation of `foldTraits` below that returns the result of
-/// folding a set of trait types `Ts` that implement a `foldTrait` method.
+/// Given a tuple type containing a set of traits, return the result of folding
+/// the given operation.
 template <typename... Ts>
-static LogicalResult foldTraitsImpl(Operation *op, ArrayRef<Attribute> operands,
-                                    SmallVectorImpl<OpFoldResult> &results,
-                                    std::tuple<Ts...> *) {
+static LogicalResult foldTraits(Operation *op, ArrayRef<Attribute> operands,
+                                SmallVectorImpl<OpFoldResult> &results) {
   bool anyFolded = false;
   (void)std::initializer_list<int>{
       (anyFolded |= succeeded(foldTrait<Ts>(op, operands, results)), 0)...};
   return success(anyFolded);
 }
 
-/// Given a tuple type containing a set of traits that contain a `foldTrait`
-/// method, return the result of folding the given operation.
-template <typename TraitTupleT>
-static std::enable_if_t<std::tuple_size<TraitTupleT>::value != 0, LogicalResult>
-foldTraits(Operation *op, ArrayRef<Attribute> operands,
-           SmallVectorImpl<OpFoldResult> &results) {
-  return foldTraitsImpl(op, operands, results, (TraitTupleT *)nullptr);
-}
-/// A variant of the method above that is specialized when there are no traits
-/// that contain a `foldTrait` method.
-template <typename TraitTupleT>
-static std::enable_if_t<std::tuple_size<TraitTupleT>::value == 0, LogicalResult>
-foldTraits(Operation *op, ArrayRef<Attribute> operands,
-           SmallVectorImpl<OpFoldResult> &results) {
-  return failure();
-}
-
 //===----------------------------------------------------------------------===//
 // Trait Verification
 
 /// Trait to check if T provides a `verifyTrait` method.
 template <typename T, typename... Args>
 using has_verify_trait = decltype(T::verifyTrait(std::declval<Operation *>()));
 template <typename T>
 using detect_has_verify_trait = llvm::is_detected<has_verify_trait, T>;
 
 /// Trait to check if T provides a `verifyTrait` method.
 template <typename T, typename... Args>
 using has_verify_region_trait =
     decltype(T::verifyRegionTrait(std::declval<Operation *>()));
 template <typename T>
 using detect_has_verify_region_trait =
     llvm::is_detected<has_verify_region_trait, T>;
 
-/// The internal implementation of `verifyTraits` below that returns the result
-/// of verifying the current operation with all of the provided trait types
-/// `Ts`.
+/// Verify the given trait if it provides a verifier.
+template <typename T>
+std::enable_if_t<detect_has_verify_trait<T>::value, LogicalResult>
+verifyTrait(Operation *op) {
+  return T::verifyTrait(op);
+}
+template <typename T>
+inline std::enable_if_t<!detect_has_verify_trait<T>::value, LogicalResult>
+verifyTrait(Operation *) {
+  return success();
+}
+
+/// Given a set of traits, return the result of verifying the given operation.
 template <typename... Ts>
-static LogicalResult verifyTraitsImpl(Operation *op, std::tuple<Ts...> *) {
+LogicalResult verifyTraits(Operation *op) {
   LogicalResult result = success();
   (void)std::initializer_list<int>{
-      (result = succeeded(result) ? Ts::verifyTrait(op) : failure(), 0)...};
+      (result = succeeded(result) ? verifyTrait<Ts>(op) : failure(), 0)...};
   return result;
 }
 
-/// Given a tuple type containing a set of traits that contain a
-/// `verifyTrait` method, return the result of verifying the given operation.
-template <typename TraitTupleT>
-static LogicalResult verifyTraits(Operation *op) {
-  return verifyTraitsImpl(op, (TraitTupleT *)nullptr);
+/// Verify the given trait if it provides a region verifier.
+template <typename T>
+std::enable_if_t<detect_has_verify_region_trait<T>::value, LogicalResult>
+verifyRegionTrait(Operation *op) {
+  return T::verifyRegionTrait(op);
+}
+template <typename T>
+inline std::enable_if_t<!detect_has_verify_region_trait<T>::value,
+                        LogicalResult>
+verifyRegionTrait(Operation *) {
+  return success();
 }
 
-/// The internal implementation of `verifyRegionTraits` below that returns the
-/// result of verifying the current operation with all of the provided trait
-/// types `Ts`.
+/// Given a set of traits, return the result of verifying the regions of the
+/// given operation.
 template <typename... Ts>
-static LogicalResult verifyRegionTraitsImpl(Operation *op,
-                                            std::tuple<Ts...> *) {
+LogicalResult verifyRegionTraits(Operation *op) {
   (void)op;
   LogicalResult result = success();
   (void)std::initializer_list<int>{
-      (result = succeeded(result) ? Ts::verifyRegionTrait(op) : failure(),
+      (result = succeeded(result) ? verifyRegionTrait<Ts>(op) : failure(),
        0)...};
   return result;
 }
-
-/// Given a tuple type containing a set of traits that contain a
-/// `verifyTrait` method, return the result of verifying the given operation.
-template <typename TraitTupleT>
-static LogicalResult verifyRegionTraits(Operation *op) {
-  return verifyRegionTraitsImpl(op, (TraitTupleT *)nullptr);
-}
 } // namespace op_definition_impl
 
 //===----------------------------------------------------------------------===//
 // Operation Definition classes
 //===----------------------------------------------------------------------===//
 
 /// This provides public APIs that all operations should have.  The template
 /// argument 'ConcreteType' should be the concrete type by CRTP and the others
private:
   template <typename T>
   using detect_has_fold = llvm::is_detected<has_fold, T>;
   /// Trait to check if T provides a 'print' method.
   template <typename T, typename... Args>
   using has_print =
       decltype(std::declval<T>().print(std::declval<OpAsmPrinter &>()));
   template <typename T>
   using detect_has_print = llvm::is_detected<has_print, T>;
-  /// A tuple type containing the traits that have a `foldTrait` function.
-  using FoldableTraitsTupleT = typename detail::FilterTypes<
-      op_definition_impl::detect_has_any_fold_trait,
-      Traits<ConcreteType>...>::type;
-  /// A tuple type containing the traits that have a verify function.
-  using VerifiableTraitsTupleT =
-      typename detail::FilterTypes<op_definition_impl::detect_has_verify_trait,
-                                   Traits<ConcreteType>...>::type;
-  /// A tuple type containing the region traits that have a verify function.
-  using VerifiableRegionTraitsTupleT = typename detail::FilterTypes<
-      op_definition_impl::detect_has_verify_region_trait,
-      Traits<ConcreteType>...>::type;
 
   /// Returns an interface map containing the interfaces registered to this
   /// operation.
   static detail::InterfaceMap getInterfaceMap() {
     return detail::InterfaceMap::template get<Traits<ConcreteType>...>();
   }
 
   /// Return the internal implementations of each of the OperationName
private:
   template <typename ConcreteOpT>
   static std::enable_if_t<!detect_has_single_result_fold<ConcreteOpT>::value &&
                               !detect_has_fold<ConcreteOpT>::value,
                           OperationName::FoldHookFn>
   getFoldHookFnImpl() {
     return [](Operation *op, ArrayRef<Attribute> operands,
               SmallVectorImpl<OpFoldResult> &results) {
       // In this case, we only need to fold the traits of the operation.
-      return op_definition_impl::foldTraits<FoldableTraitsTupleT>(op, operands,
-                                                                  results);
+      return op_definition_impl::foldTraits<Traits<ConcreteType>...>(
+          op, operands, results);
     };
   }
   /// Return the result of folding a single result operation that defines a
   /// `fold` method.
   template <typename ConcreteOpT>
   static LogicalResult
   foldSingleResultHook(Operation *op, ArrayRef<Attribute> operands,
                        SmallVectorImpl<OpFoldResult> &results) {
     OpFoldResult result = cast<ConcreteOpT>(op).fold(operands);
 
     // If the fold failed or was in-place, try to fold the traits of the
     // operation.
     if (!result || result.template dyn_cast<Value>() == op->getResult(0)) {
-      if (succeeded(op_definition_impl::foldTraits<FoldableTraitsTupleT>(
+      if (succeeded(op_definition_impl::foldTraits<Traits<ConcreteType>...>(
               op, operands, results)))
         return success();
       return success(static_cast<bool>(result));
     }
     results.push_back(result);
     return success();
   }
   /// Return the result of folding an operation that defines a `fold` method.
   template <typename ConcreteOpT>
   static LogicalResult foldHook(Operation *op, ArrayRef<Attribute> operands,
                                 SmallVectorImpl<OpFoldResult> &results) {
     LogicalResult result = cast<ConcreteOpT>(op).fold(operands, results);
 
     // If the fold failed or was in-place, try to fold the traits of the
     // operation.
     if (failed(result) || results.empty()) {
-      if (succeeded(op_definition_impl::foldTraits<FoldableTraitsTupleT>(
+      if (succeeded(op_definition_impl::foldTraits<Traits<ConcreteType>...>(
               op, operands, results)))
         return success();
     }
     return result;
   }
 
   /// Implementation of `GetCanonicalizationPatternsFn` OperationName hook.
   static OperationName::GetCanonicalizationPatternsFn
static void printAssembly(Operation *op, OpAsmPrinter &p,
     OpState::printOpName(op, p, defaultDialect);
     return cast<ConcreteType>(op).print(p);
   }
   /// Implementation of `VerifyInvariantsFn` OperationName hook.
   static LogicalResult verifyInvariants(Operation *op) {
     static_assert(hasNoDataMembers(),
                   "Op class shouldn't define new data members");
     return failure(
-        failed(op_definition_impl::verifyTraits<VerifiableTraitsTupleT>(op)) ||
+        failed(op_definition_impl::verifyTraits<Traits<ConcreteType>...>(op)) ||
         failed(cast<ConcreteType>(op).verify()));
   }
   static OperationName::VerifyInvariantsFn getVerifyInvariantsFn() {
     return static_cast<LogicalResult (*)(Operation *)>(&verifyInvariants);
   }
   /// Implementation of `VerifyRegionInvariantsFn` OperationName hook.
   static LogicalResult verifyRegionInvariants(Operation *op) {
     static_assert(hasNoDataMembers(),
                   "Op class shouldn't define new data members");
-    return failure(failed(op_definition_impl::verifyRegionTraits<
-                          VerifiableRegionTraitsTupleT>(op)) ||
-                   failed(cast<ConcreteType>(op).verifyRegions()));
+    return failure(
+        failed(op_definition_impl::verifyRegionTraits<Traits<ConcreteType>...>(
+            op)) ||
   }
   static OperationName::VerifyRegionInvariantsFn getVerifyRegionInvariantsFn() {
     return static_cast<LogicalResult (*)(Operation *)>(&verifyRegionInvariants);
   }
 
   static constexpr bool hasNoDataMembers() {
     // Checking that the derived class does not define any member by comparing
     // its size to an ad-hoc EmptyOp.

mlir/include/mlir/Support/InterfaceSupport.h

private:
   /// A pointer to the impl concept object.
   Concept *impl;
 };
 
 //===----------------------------------------------------------------------===//
 // InterfaceMap
 //===----------------------------------------------------------------------===//
 
-/// Utility to filter a given sequence of types base upon a predicate.
-template <bool>
-struct FilterTypeT {
-  template <class E>
-  using type = std::tuple<E>;
-};
-template <>
-struct FilterTypeT<false> {
-  template <class E>
-  using type = std::tuple<>;
-};
-template <template <class> class Pred, class... Es>
-struct FilterTypes {
-  using type = decltype(std::tuple_cat(
-      std::declval<
-          typename FilterTypeT<Pred<Es>::value>::template type<Es>>()...));
-};
+/// Template utility that computes the number of elements within `T` that
+/// satisfy the given predicate.
+template <template <class> class Pred, size_t N, typename... Ts>
+struct count_if_t_impl : public std::integral_constant<size_t, N> {};
+template <template <class> class Pred, size_t N, typename T, typename... Us>
+struct count_if_t_impl<Pred, N, T, Us...>
+    : public std::integral_constant<
+          size_t,
+          count_if_t_impl<Pred, N + (Pred<T>::value ? 1 : 0), Us...>::value> {};
+template <template <class> class Pred, typename... Ts>
+using count_if_t = count_if_t_impl<Pred, 0, Ts...>;
 
 namespace {
 /// Type trait indicating whether all template arguments are
 /// trivially-destructible.
 template <typename... Args>
 struct all_trivially_destructible;
 
 template <typename Arg, typename... Args>

 /// and a particular implementation of its concept.
 class InterfaceMap {
   /// Trait to check if T provides a static 'getInterfaceID' method.
   template <typename T, typename... Args>
   using has_get_interface_id = decltype(T::getInterfaceID());
   template <typename T>
   using detect_get_interface_id = llvm::is_detected<has_get_interface_id, T>;
   template <typename... Types>
-  using num_interface_types = typename std::tuple_size<
-      typename FilterTypes<detect_get_interface_id, Types...>::type>;
+  using num_interface_types_t = count_if_t<detect_get_interface_id, Types...>;
 
 public:
   InterfaceMap(InterfaceMap &&) = default;
   InterfaceMap &operator=(InterfaceMap &&rhs) {
     for (auto &it : interfaces)
       free(it.second);
     interfaces = std::move(rhs.interfaces);
     return *this;
   }
   ~InterfaceMap() {
     for (auto &it : interfaces)
       free(it.second);
   }
 
   /// Construct an InterfaceMap with the given set of template types. For
   /// convenience given that object trait lists may contain other non-interface
   /// types, not all of the types need to be interfaces. The provided types that
   /// do not represent interfaces are not added to the interface map.
   template <typename... Types>
-  static std::enable_if_t<num_interface_types<Types...>::value != 0,
-                          InterfaceMap>
-  get() {
-    // Filter the provided types for those that are interfaces.
-    using FilteredTupleType =
-        typename FilterTypes<detect_get_interface_id, Types...>::type;
-    return getImpl((FilteredTupleType *)nullptr);
-  }
-
-  template <typename... Types>
-  static std::enable_if_t<num_interface_types<Types...>::value == 0,
-                          InterfaceMap>
-  get() {
+  static InterfaceMap get() {
+    // TODO: Use constexpr if here in C++17.
+    constexpr size_t numInterfaces = num_interface_types_t<Types...>::value;
+    if (numInterfaces == 0)
       return InterfaceMap();
+
+    std::array<std::pair<TypeID, void *>, numInterfaces> elements;
+    std::pair<TypeID, void *> *elementIt = elements.data();
+    (void)std::initializer_list<int>{
+        0, (addModelAndUpdateIterator<Types>(elementIt), 0)...};
+    return InterfaceMap(elements);
   }
 
   /// Returns an instance of the concept object for the given interface if it
   /// was registered to this map, null otherwise.
   template <typename T> typename T::Concept *lookup() const {
     return reinterpret_cast<typename T::Concept *>(lookup(T::getInterfaceID()));
   }
 
static_assert(all_trivially_destructible<IfaceModels...>::value,
                   "interface models must be trivially destructible");
     std::pair<TypeID, void *> elements[] = {
         std::make_pair(IfaceModels::Interface::getInterfaceID(),
                        new (malloc(sizeof(IfaceModels))) IfaceModels())...};
     insert(elements);
   }
 
 private:
-  /// Compare two TypeID instances by comparing the underlying pointer.
-  static bool compare(TypeID lhs, TypeID rhs) {
-    return lhs.getAsOpaquePointer() < rhs.getAsOpaquePointer();
-  }
-
   InterfaceMap() = default;
 
+  /// Assign the interface model of the type to the given opaque element
+  /// iterator and increment it.
+  template <typename T>
+  static inline std::enable_if_t<detect_get_interface_id<T>::value>
+  addModelAndUpdateIterator(std::pair<TypeID, void *> *&elementIt) {
+    *elementIt = {T::getInterfaceID(), new (malloc(sizeof(typename T::ModelT)))
+                                           typename T::ModelT()};
+    ++elementIt;
+  }
+  /// Overload when `T` isn't an interface.
+  template <typename T>
+  static inline std::enable_if_t<!detect_get_interface_id<T>::value>
+  addModelAndUpdateIterator(std::pair<TypeID, void *> *&) {}
+
+  /// Insert the given set of interface models into the interface map.
   void insert(ArrayRef<std::pair<TypeID, void *>> elements);
 
-  template <typename... Ts>
-  static InterfaceMap getImpl(std::tuple<Ts...> *) {
-    std::pair<TypeID, void *> elements[] = {std::make_pair(
-        Ts::getInterfaceID(),
-        new (malloc(sizeof(typename Ts::ModelT))) typename Ts::ModelT())...};
-    return InterfaceMap(elements);
+  /// Compare two TypeID instances by comparing the underlying pointer.
+  static bool compare(TypeID lhs, TypeID rhs) {
+    return lhs.getAsOpaquePointer() < rhs.getAsOpaquePointer();
   }
 
   /// Returns an instance of the concept object for the given interface id if it
   /// was registered to this map, null otherwise.
   void *lookup(TypeID id) const {
     const auto *it =
         llvm::lower_bound(interfaces, id, [](const auto &it, TypeID id) {
           return compare(it.first, id);