[analysis][NFC] Use C++20 concepts for Lattice (#6027)

Replace the static assertions ensuring that Lattice types have the necessary
operations with a C++20 concept called `Lattice`. To avoid name conflicts with
the new concept, rename existing type parameters named `Lattice` to `L`. When
not building with C++20, `Lattice` is a macro that resolves to `typename` so the
code continues compiling and has the same behavior, but without any eager checks
of the requirements on lattices.

Add a new C++20 builder to CI to ensure that future changes compile with both
C++17 and C++20. Once we switch to C++20 by default, the new builder can be
removed. Update the lint builder to use a recent clang-format that understands
concepts.

6 files changed, 80 insertions, 90 deletions

diff --git a/src/analysis/lattice.h b/src/analysis/lattice.h
index 1f2669c89..354447efc 100644
--- a/src/analysis/lattice.h
+++ b/src/analysis/lattice.h
@@ -23,35 +23,33 @@ inline LatticeComparison reverseComparison(LatticeComparison comparison) {
   }
 }
 
-template<typename Lattice>
-constexpr bool has_getBottom =
-  std::is_invocable_r<typename Lattice::Element,
-                      decltype(&Lattice::getBottom),
-                      Lattice>::value;
-template<typename Lattice>
-constexpr bool has_compare =
-  std::is_invocable_r<LatticeComparison,
-                      decltype(&Lattice::compare),
-                      Lattice,
-                      const typename Lattice::Element&,
-                      const typename Lattice::Element&>::value;
-template<typename Element>
-constexpr bool has_makeLeastUpperBound =
-  std::is_invocable_r<void,
-                      decltype(&Element::makeLeastUpperBound),
-                      Element,
-                      const Element&>::value;
-template<typename Element>
-constexpr bool has_isTop =
-  std::is_invocable_r<bool, decltype(&Element::isTop), const Element>::value;
-template<typename Element>
-constexpr bool has_isBottom =
-  std::is_invocable_r<bool, decltype(&Element::isBottom), const Element>::value;
-
-template<typename Lattice>
-constexpr bool is_lattice = has_getBottom<Lattice>&& has_compare<Lattice>&&
-  has_makeLeastUpperBound<typename Lattice::Element>&& has_isTop<
-    typename Lattice::Element>&& has_isBottom<typename Lattice::Element>;
+#if __cplusplus >= 202002L
+
+#include <concepts>
+
+template<typename L>
+concept Lattice = requires(const L& lattice,
+                           const typename L::Element& constElem,
+                           typename L::Element& elem) {
+  // Lattices must have elements.
+  typename L::Element;
+  // We need to be able to get the bottom element.
+  { lattice.getBottom() } noexcept -> std::same_as<typename L::Element>;
+  // Elements should be comparable. TODO: use <=> and std::three_way_comparable
+  // once we support C++20 everywhere.
+  {
+    lattice.compare(constElem, constElem)
+  } noexcept -> std::same_as<LatticeComparison>;
+  // We need to be able to get the least upper bound of two elements and know
+  // whether any change was made.
+  { elem.makeLeastUpperBound(constElem) } noexcept -> std::same_as<bool>;
+};
+
+#else
+
+#define Lattice typename
+
+#endif // __cplusplus >= 202002L
 
 // Represents a powerset lattice constructed from a finite set of consecutive
 // integers from 0 to n which can be represented by a bitvector. Set elements
@@ -101,7 +99,7 @@ public:
     // Calculates the LUB of this element with some other element and sets
     // this element to the LUB in place. Returns true if this element before
     // this method call was different than the LUB.
-    bool makeLeastUpperBound(const Element& other);
+    bool makeLeastUpperBound(const Element& other) noexcept;
 
     // Prints out the bits in the bitvector for a lattice element.
     void print(std::ostream& os);
@@ -111,10 +109,11 @@ public:
 
   // Compares two lattice elements and returns a result indicating the
   // left element's relation to the right element.
-  LatticeComparison compare(const Element& left, const Element& right);
+  LatticeComparison compare(const Element& left,
+                            const Element& right) const noexcept;
 
   // Returns an instance of the bottom lattice element.
-  Element getBottom();
+  Element getBottom() const noexcept;
 };
 
 // A layer of abstraction over FiniteIntPowersetLattice which maps
@@ -169,11 +168,12 @@ public:
   }
 
   // We use implementations from FiniteIntPowersetLattice here.
-  LatticeComparison compare(const Element& left, const Element& right) {
+  LatticeComparison compare(const Element& left,
+                            const Element& right) const noexcept {
     return intLattice.compare(left, right);
   }
 
-  Element getBottom() { return intLattice.getBottom(); }
+  Element getBottom() const noexcept { return intLattice.getBottom(); }
 };
 
 } // namespace wasm::analysis
diff --git a/src/analysis/monotone-analyzer-impl.h b/src/analysis/monotone-analyzer-impl.h
index 8599bccf2..a87ba4282 100644
--- a/src/analysis/monotone-analyzer-impl.h
+++ b/src/analysis/monotone-analyzer-impl.h
@@ -10,14 +10,12 @@ namespace wasm::analysis {
 
 // All states are set to the bottom lattice element using the lattice in this
 // constructor.
-template<typename Lattice>
-inline BlockState<Lattice>::BlockState(const BasicBlock* underlyingBlock,
-                                       Lattice& lattice)
+template<Lattice L>
+inline BlockState<L>::BlockState(const BasicBlock* underlyingBlock, L& lattice)
   : cfgBlock(underlyingBlock), inputState(lattice.getBottom()) {}
 
 // Prints out inforamtion about a CFG node's state, but not intermediate states.
-template<typename Lattice>
-inline void BlockState<Lattice>::print(std::ostream& os) {
+template<Lattice L> inline void BlockState<L>::print(std::ostream& os) {
   os << "CFG Block: " << cfgBlock->getIndex() << std::endl;
   os << "Input State: ";
   inputState.print(os);
@@ -32,9 +30,9 @@ inline void BlockState<Lattice>::print(std::ostream& os) {
   os << std::endl;
 }
 
-template<typename Lattice, typename TransferFunction>
-inline MonotoneCFGAnalyzer<Lattice, TransferFunction>::MonotoneCFGAnalyzer(
-  Lattice& lattice, TransferFunction& transferFunction, CFG& cfg)
+template<Lattice L, typename TransferFunction>
+inline MonotoneCFGAnalyzer<L, TransferFunction>::MonotoneCFGAnalyzer(
+  L& lattice, TransferFunction& transferFunction, CFG& cfg)
   : lattice(lattice), transferFunction(transferFunction), cfg(cfg) {
 
   // Construct BlockStates for each BasicBlock.
@@ -43,30 +41,28 @@ inline MonotoneCFGAnalyzer<Lattice, TransferFunction>::MonotoneCFGAnalyzer(
   }
 }
 
-template<typename Lattice, typename TransferFunction>
-inline void
-MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluateFunctionEntry(
+template<Lattice L, typename TransferFunction>
+inline void MonotoneCFGAnalyzer<L, TransferFunction>::evaluateFunctionEntry(
   Function* func) {
   transferFunction.evaluateFunctionEntry(func, stateBlocks[0].inputState);
 }
 
-template<typename Lattice, typename TransferFunction>
-inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluate() {
+template<Lattice L, typename TransferFunction>
+inline void MonotoneCFGAnalyzer<L, TransferFunction>::evaluate() {
   std::queue<const BasicBlock*> worklist;
 
   // Transfer function enqueues the work in some order which is efficient.
   transferFunction.enqueueWorklist(cfg, worklist);
 
   while (!worklist.empty()) {
-    BlockState<Lattice>& currBlockState =
-      stateBlocks[worklist.front()->getIndex()];
+    BlockState<L>& currBlockState = stateBlocks[worklist.front()->getIndex()];
     worklist.pop();
 
     // For each expression, applies the transfer function, using the expression,
     // on the state of the expression it depends upon (here the next expression)
     // to arrive at the expression's state. The beginning and end states of the
     // CFG block will be updated.
-    typename Lattice::Element outputState = currBlockState.inputState;
+    typename L::Element outputState = currBlockState.inputState;
     transferFunction.transfer(currBlockState.cfgBlock, outputState);
 
     // Propagate state to dependents of currBlockState.
@@ -81,10 +77,10 @@ inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::evaluate() {
   }
 }
 
-template<typename Lattice, typename TransferFunction>
-inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::collectResults() {
+template<Lattice L, typename TransferFunction>
+inline void MonotoneCFGAnalyzer<L, TransferFunction>::collectResults() {
   for (BlockState currBlockState : stateBlocks) {
-    typename Lattice::Element inputStateCopy = currBlockState.inputState;
+    typename L::Element inputStateCopy = currBlockState.inputState;
 
     // The transfer function generates the final set of states and uses it to
     // produce useful information. For example, in reaching definitions
@@ -96,13 +92,12 @@ inline void MonotoneCFGAnalyzer<Lattice, TransferFunction>::collectResults() {
 
 // Currently prints both the basic information and intermediate states of each
 // BlockState.
-template<typename Lattice, typename TransferFunction>
-inline void
-MonotoneCFGAnalyzer<Lattice, TransferFunction>::print(std::ostream& os) {
+template<Lattice L, typename TransferFunction>
+inline void MonotoneCFGAnalyzer<L, TransferFunction>::print(std::ostream& os) {
   os << "CFG Analyzer" << std::endl;
   for (auto state : stateBlocks) {
     state.print(os);
-    typename Lattice::Element temp = state.inputState;
+    typename L::Element temp = state.inputState;
     transferFunction.print(os, state.cfgBlock, temp);
   }
   os << "End" << std::endl;
diff --git a/src/analysis/monotone-analyzer.h b/src/analysis/monotone-analyzer.h
index 2b0e0ae16..480cf2185 100644
--- a/src/analysis/monotone-analyzer.h
+++ b/src/analysis/monotone-analyzer.h
@@ -11,17 +11,16 @@
 namespace wasm::analysis {
 
 // A node which contains all the lattice states for a given CFG node.
-template<typename Lattice> struct BlockState {
-  static_assert(is_lattice<Lattice>);
+template<Lattice L> struct BlockState {
 
   // CFG node corresponding to this state block.
   const BasicBlock* cfgBlock;
   // State at which the analysis flow starts for a CFG. For instance, the ending
   // state for backward analysis, or the beginning state for forward analysis.
-  typename Lattice::Element inputState;
+  typename L::Element inputState;
 
   // All states are set to the bottom lattice element in this constructor.
-  BlockState(const BasicBlock* underlyingBlock, Lattice& lattice);
+  BlockState(const BasicBlock* underlyingBlock, L& lattice);
 
   // Prints out BlockState information, but not any intermediate states.
   void print(std::ostream& os);
@@ -42,13 +41,13 @@ template<typename Lattice> struct BlockState {
 // propagated to dependents of the CFG BasicBlock by the worklist algorithm in
 // MonotoneCFGAnalyzer.
 
-template<typename TransferFunction, typename Lattice>
+template<typename TransferFunction, Lattice L>
 constexpr bool has_transfer =
   std::is_invocable_r<void,
                       decltype(&TransferFunction::transfer),
                       TransferFunction,
                       const BasicBlock*,
-                      typename Lattice::Element&>::value;
+                      typename L::Element&>::value;
 
 // void enqueueWorklist(CFG&, std::queue<const BasicBlock*>& value);
 
@@ -58,7 +57,7 @@ constexpr bool has_transfer =
 // state propagations, and therefore better performance. The opposite is true
 // for a forward analysis.
 
-template<typename TransferFunction, typename Lattice>
+template<typename TransferFunction, Lattice L>
 constexpr bool has_enqueueWorklist =
   std::is_invocable_r<void,
                       decltype(&TransferFunction::enqueueWorklist),
@@ -80,27 +79,23 @@ constexpr bool has_getDependents =
                       const BasicBlock*>::value;
 
 // Combined TransferFunction assertions.
-template<typename TransferFunction, typename Lattice>
-constexpr bool is_TransferFunction = has_transfer<TransferFunction, Lattice>&&
-  has_enqueueWorklist<TransferFunction, Lattice>&&
-    has_getDependents<TransferFunction>;
+template<typename TransferFunction, Lattice L>
+constexpr bool is_TransferFunction = has_transfer<TransferFunction, L> &&
+                                     has_enqueueWorklist<TransferFunction, L> &&
+                                     has_getDependents<TransferFunction>;
 
-template<typename Lattice, typename TransferFunction>
-class MonotoneCFGAnalyzer {
-  static_assert(is_lattice<Lattice>);
-  static_assert(is_TransferFunction<TransferFunction, Lattice>);
+template<Lattice L, typename TransferFunction> class MonotoneCFGAnalyzer {
+  static_assert(is_TransferFunction<TransferFunction, L>);
 
-  Lattice& lattice;
+  L& lattice;
   TransferFunction& transferFunction;
   CFG& cfg;
-  std::vector<BlockState<Lattice>> stateBlocks;
+  std::vector<BlockState<L>> stateBlocks;
 
 public:
   // Will constuct BlockState objects corresponding to BasicBlocks from the
   // given CFG.
-  MonotoneCFGAnalyzer(Lattice& lattice,
-                      TransferFunction& transferFunction,
-                      CFG& cfg);
+  MonotoneCFGAnalyzer(L& lattice, TransferFunction& transferFunction, CFG& cfg);
 
   // Runs the worklist algorithm to compute the states for the BlockState graph.
   void evaluate();
diff --git a/src/analysis/powerset-lattice-impl.h b/src/analysis/powerset-lattice-impl.h
index 6d710826b..33ebd312f 100644
--- a/src/analysis/powerset-lattice-impl.h
+++ b/src/analysis/powerset-lattice-impl.h
@@ -7,7 +7,7 @@ namespace wasm::analysis {
 
 inline LatticeComparison FiniteIntPowersetLattice::compare(
   const FiniteIntPowersetLattice::Element& left,
-  const FiniteIntPowersetLattice::Element& right) {
+  const FiniteIntPowersetLattice::Element& right) const noexcept {
   // Both must be from the powerset lattice of the same set.
   assert(left.bitvector.size() == right.bitvector.size());
 
@@ -41,7 +41,8 @@ inline LatticeComparison FiniteIntPowersetLattice::compare(
   return NO_RELATION;
 }
 
-inline FiniteIntPowersetLattice::Element FiniteIntPowersetLattice::getBottom() {
+inline FiniteIntPowersetLattice::Element
+FiniteIntPowersetLattice::getBottom() const noexcept {
   FiniteIntPowersetLattice::Element result(setSize);
   return result;
 }
@@ -60,7 +61,7 @@ inline size_t FiniteIntPowersetLattice::Element::count() const {
 // both sides. We return true if a bit is flipped in-place on the left so the
 // worklist algorithm will know if when to enqueue more work.
 inline bool FiniteIntPowersetLattice::Element::makeLeastUpperBound(
-  const FiniteIntPowersetLattice::Element& other) {
+  const FiniteIntPowersetLattice::Element& other) noexcept {
   // Both must be from powerset lattice of the same set.
   assert(other.bitvector.size() == bitvector.size());
 
diff --git a/src/analysis/stack-lattice.h b/src/analysis/stack-lattice.h
index 069dfa8ab..e27e01a2f 100644
--- a/src/analysis/stack-lattice.h
+++ b/src/analysis/stack-lattice.h
@@ -65,8 +65,7 @@ namespace wasm::analysis {
 // produce a stack [b, LUB(a, a')], where LUB(a, a') takes the maximum
 // of the two maximum bit values.
 
-template<typename StackElementLattice> class StackLattice {
-  static_assert(is_lattice<StackElementLattice>);
+template<Lattice StackElementLattice> class StackLattice {
   StackElementLattice& stackElementLattice;
 
 public:
@@ -127,7 +126,7 @@ public:
     // fits with the conception of the stack starting at the top and having
     // an infinite bottom, which allows stacks of different height and scope
     // to be easily joined.
-    bool makeLeastUpperBound(const Element& other) {
+    bool makeLeastUpperBound(const Element& other) noexcept {
       // Top element cases, since top elements don't actually have the stack
       // value.
       if (isTop()) {
@@ -185,7 +184,8 @@ public:
   // >= right top or if the left stack is higher and the right top > left top or
   // they are unrelated, then there is no relation. Same applies for the reverse
   // relationship.
-  LatticeComparison compare(const Element& left, const Element& right) {
+  LatticeComparison compare(const Element& left,
+                            const Element& right) const noexcept {
     // Handle cases where there are top elements.
     if (left.isTop()) {
       if (right.isTop()) {
@@ -246,7 +246,7 @@ public:
     }
   }
 
-  Element getBottom() { return Element{}; }
+  Element getBottom() const noexcept { return Element{}; }
 };
 
 } // namespace wasm::analysis
diff --git a/src/analysis/visitor-transfer-function.h b/src/analysis/visitor-transfer-function.h
index 18ee35392..699840ff3 100644
--- a/src/analysis/visitor-transfer-function.h
+++ b/src/analysis/visitor-transfer-function.h
@@ -14,10 +14,10 @@ enum class AnalysisDirection { Forward, Backward };
 // Utility for visitor-based transfer functions for forward and backward
 // analysis. Forward analysis is chosen by default unless the template parameter
 // Backward is true.
-template<typename SubType, typename Lattice, AnalysisDirection Direction>
+template<typename SubType, Lattice L, AnalysisDirection Direction>
 struct VisitorTransferFunc : public Visitor<SubType> {
 protected:
-  typename Lattice::Element* currState = nullptr;
+  typename L::Element* currState = nullptr;
 
   // There are two distinct phases in the execution of the analyzer. First,
   // the worklist algorithm will be run to obtain a solution, calling
@@ -46,8 +46,7 @@ public:
   // Executes the transfer function on all the expressions of the corresponding
   // CFG node, starting with the node's input state, and changes the input state
   // to the final output state of the node in place.
-  void transfer(const BasicBlock* cfgBlock,
-                typename Lattice::Element& inputState) {
+  void transfer(const BasicBlock* cfgBlock, typename L::Element& inputState) {
     // If the block is empty, we propagate the state by inputState =
     // outputState.
 
@@ -87,7 +86,7 @@ public:
   // This is for collecting results after solving an analysis. Implemented in
   // the same way as transfer(), but we also set the collectingResults flag.
   void collectResults(const BasicBlock* cfgBlock,
-                      typename Lattice::Element& inputState) {
+                      typename L::Element& inputState) {
     collectingResults = true;
     currState = &inputState;
     if constexpr (Direction == AnalysisDirection::Backward) {