Index: llvm/include/llvm/Support/TypeSize.h
===================================================================
--- llvm/include/llvm/Support/TypeSize.h
+++ llvm/include/llvm/Support/TypeSize.h
@@ -15,69 +15,287 @@
 #ifndef LLVM_SUPPORT_TYPESIZE_H
 #define LLVM_SUPPORT_TYPESIZE_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/WithColor.h"
 
-#include <cstdint>
+#include <algorithm>
+#include <array>
 #include <cassert>
+#include <cstdint>
+#include <type_traits>
 
 namespace llvm {
 
-template <typename T> struct DenseMapInfo;
+template <typename LeafTy> struct LinearPolyBaseTypeTraits {};
+
+//===----------------------------------------------------------------------===//
+// LinearPolyBase - a base class for linear polynomials with multiple
+// dimensions. This can e.g. be used to describe offsets that are have both a
+// fixed and scalable component.
+//===----------------------------------------------------------------------===//
+
+/// LinearPolyBase describes a linear polynomial:
+///  c0 * scale0 + c1 * scale1 + ... + cK * scaleK
+/// where the scale is implicit, so only the coefficients are encoded.
+template <typename LeafTy>
+class LinearPolyBase {
+public:
+  using ScalarTy = typename LinearPolyBaseTypeTraits<LeafTy>::ScalarTy;
+  static constexpr auto Dimensions = LinearPolyBaseTypeTraits<LeafTy>::Dimensions;
+  static_assert(Dimensions != std::numeric_limits<unsigned>::max(),
+                "Dimensions out of range");
+
+private:
+  std::array<ScalarTy, Dimensions> Coefficients;
+
+protected:
+  LinearPolyBase(ArrayRef<ScalarTy> Values) {
+    std::copy(Values.begin(), Values.end(), Coefficients.begin());
+  }
+
+public:
+  friend LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) {
+    for (unsigned I=0; I<Dimensions; ++I)
+      LHS.Coefficients[I] += RHS.Coefficients[I];
+    return LHS;
+  }
+
+  friend LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) {
+    for (unsigned I=0; I<Dimensions; ++I)
+      LHS.Coefficients[I] -= RHS.Coefficients[I];
+    return LHS;
+  }
+
+  friend LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) {
+    for (auto &C : LHS.Coefficients)
+      C *= RHS;
+    return LHS;
+  }
+
+  friend LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) {
+    LeafTy Copy = LHS;
+    return Copy += RHS;
+  }
+
+  friend LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) {
+    LeafTy Copy = LHS;
+    return Copy -= RHS;
+  }
+
+  friend LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) {
+    LeafTy Copy = LHS;
+    return Copy *= RHS;
+  }
+
+  template <typename U = ScalarTy>
+  friend typename std::enable_if_t<std::is_signed<U>::value, LeafTy>
+  operator-(const LeafTy &LHS) {
+    LeafTy Copy = LHS;
+    return Copy *= -1;
+  }
+
+  bool operator==(const LinearPolyBase &RHS) const {
+    return std::equal(Coefficients.begin(), Coefficients.end(),
+                      RHS.Coefficients.begin());
+  }
+
+  bool operator!=(const LinearPolyBase &RHS) const {
+    return !(*this == RHS);
+  }
+
+  bool isZero() const {
+    return all_of(Coefficients, [](const ScalarTy &C) { return C == 0; });
+  }
+  bool isNonZero() const { return !isZero(); }
+  explicit operator bool() const { return isNonZero(); }
+
+  ScalarTy getValue(unsigned Dim) const { return Coefficients[Dim]; }
+};
+
+//===----------------------------------------------------------------------===//
+// StackOffset - Represent an offset with named fixed and scalable components.
+//===----------------------------------------------------------------------===//
+
+namespace NewStackOffset {
+class StackOffset;
+} // end namespace NewStackOffset
+
+template <> struct LinearPolyBaseTypeTraits<NewStackOffset::StackOffset> {
+  using ScalarTy = int64_t;
+  static constexpr unsigned Dimensions = 2;
+};
+
+namespace NewStackOffset {
 
-// TODO: This class will be redesigned in a later patch that introduces full
-// polynomial behaviour, i.e. the ability to have composites made up of both
-// fixed and scalable sizes.
-template <typename T> class PolySize {
+/// StackOffset is a class to represent an offset with 2 dimensions,
+/// named fixed and scalable, respectively. This class allows a value for both
+/// dimensions to depict e.g. "8 bytes and 16 scalable bytes", which is needed
+/// to represent stack offsets.
+class StackOffset : public LinearPolyBase<StackOffset> {
 protected:
-  T MinVal;        // The minimum value that it could be.
-  bool IsScalable; // If true, the total value is determined by multiplying
-                   // 'MinVal' by a runtime determinded quantity, 'vscale'.
+  StackOffset(ScalarTy Fixed, ScalarTy Scalable)
+      : LinearPolyBase<StackOffset>({Fixed, Scalable}) {}
+
+public:
+  StackOffset() : StackOffset({0, 0}) {}
+  StackOffset(const LinearPolyBase<StackOffset> &Other)
+      : LinearPolyBase<StackOffset>(Other) {}
+  static StackOffset getFixed(ScalarTy Fixed) { return {Fixed, 0}; }
+  static StackOffset getScalable(ScalarTy Scalable) { return {0, Scalable}; }
+  static StackOffset get(ScalarTy Fixed, ScalarTy Scalable) {
+    return {Fixed, Scalable};
+  }
+
+  ScalarTy getFixed() const { return this->getValue(0); }
+  ScalarTy getScalable() const { return this->getValue(1); }
+};
 
-  constexpr PolySize(T MinVal, bool IsScalable)
-      : MinVal(MinVal), IsScalable(IsScalable) {}
+} // end namespace NewStackOffset
 
+
+//===----------------------------------------------------------------------===//
+// UnivariateLinearPolyBase - a base class for linear polynomials with multiple
+// dimensions, but where only one dimension can be set at any time.
+// This can e.g. be used to describe sizes that are either fixed or scalable.
+//===----------------------------------------------------------------------===//
+
+/// UnivariateLinearPolyBase is a base class for ElementCount and TypeSize.
+/// Like LinearPolyBase it tries to represent a linear polynomial
+/// where only one dimension can be set at any time, e.g.
+///   0 * scale0 + 0 * scale1 + ... + cJ * scaleJ + ... + 0 * scaleK
+/// The dimension that is set is the univariate dimension.
+template <typename LeafTy>
+class UnivariateLinearPolyBase {
 public:
+  using ScalarTy = typename LinearPolyBaseTypeTraits<LeafTy>::ScalarTy;
+  static constexpr auto Dimensions = LinearPolyBaseTypeTraits<LeafTy>::Dimensions;
+  static_assert(Dimensions != std::numeric_limits<unsigned>::max(),
+                "Dimensions out of range");
 
-  static constexpr PolySize getFixed(T MinVal) { return {MinVal, false}; }
-  static constexpr PolySize getScalable(T MinVal) { return {MinVal, true}; }
-  static constexpr PolySize get(T MinVal, bool IsScalable) {
-    return {MinVal, IsScalable};
+protected:
+  ScalarTy Value;         // The value at the univeriate dimension.
+  unsigned UnivariateDim; // The univeriate dimension.
+
+  UnivariateLinearPolyBase(ScalarTy &Val, unsigned UnivariateDim)
+      : Value(Val), UnivariateDim(UnivariateDim) {}
+
+  friend LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) {
+    assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions");
+    LHS.Value += RHS.Value;
+    return LHS;
   }
 
-  static constexpr PolySize getNull() { return {0, false}; }
+  friend LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) {
+    assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions");
+    LHS.Value -= RHS.Value;
+    return LHS;
+  }
 
-  /// Counting predicates.
-  ///
-  ///@{ No elements..
-  bool isZero() const { return MinVal == 0; }
-  /// At least one element.
+  friend LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) {
+    LHS.Value *= RHS;
+    return LHS;
+  }
+
+  friend LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) {
+    LeafTy Copy = LHS;
+    return Copy += RHS;
+  }
+
+  friend LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) {
+    LeafTy Copy = LHS;
+    return Copy -= RHS;
+  }
+
+  friend LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) {
+    LeafTy Copy = LHS;
+    return Copy *= RHS;
+  }
+
+  template <typename U = ScalarTy>
+  friend typename std::enable_if<std::is_signed<U>::value, LeafTy>::type
+  operator-(const LeafTy &LHS) {
+    LeafTy Copy = LHS;
+    return Copy *= -1;
+  }
+
+public:
+  bool operator==(const UnivariateLinearPolyBase &RHS) const {
+    return Value == RHS.Value && UnivariateDim == RHS.UnivariateDim;
+  }
+
+  bool operator!=(const UnivariateLinearPolyBase &RHS) const {
+    return !(*this == RHS);
+  }
+
+  bool isZero() const { return !Value; }
   bool isNonZero() const { return !isZero(); }
+  explicit operator bool() const { return isNonZero(); }
+  ScalarTy getValue() const { return Value; }
+  ScalarTy getValue(unsigned Dim) const {
+    return Dim == UnivariateDim ? Value : 0;
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+// LinearPolySize - base class for fixed- or scalable sizes.
+//  ^  ^ 
+//  |  |
+//  |  +----- ElementCount - Leaf class to represent an element count
+//  |                        (vscale x unsigned)
+//  |
+//  +-------- TypeSize - Leaf class to represent a type size
+//                       (vscale x uint64_t)
+//===----------------------------------------------------------------------===//
+
+/// LinearPolySize is a base class to represent sizes. It is either
+/// fixed-sized or it is scalable-sized, but it cannot be both.
+template <typename LeafTy>
+class LinearPolySize : public UnivariateLinearPolyBase<LeafTy> {
+public:
+  using ScalarTy = typename UnivariateLinearPolyBase<LeafTy>::ScalarTy;
+  enum Dims : unsigned { FixedDim = 0, ScalableDim = 1 };
+
+protected:
+  LinearPolySize(ScalarTy MinVal, Dims D)
+      : UnivariateLinearPolyBase<LeafTy>(MinVal, D) {}
+
+public:
+  static LeafTy getFixed(ScalarTy MinVal) {
+    return static_cast<LeafTy>(LinearPolySize(MinVal, FixedDim));
+  }
+  static LeafTy getScalable(ScalarTy MinVal) {
+    return static_cast<LeafTy>(LinearPolySize(MinVal, ScalableDim));
+  }
+  static LeafTy get(ScalarTy MinVal, bool Scalable) {
+    return static_cast<LeafTy>(
+        LinearPolySize(MinVal, Scalable ? ScalableDim : FixedDim));
+  }
+
+  /// Returns the minimum value this size can represent.
+  ScalarTy getKnownMinValue() const { return this->getValue(); }
+  /// Returns whether the size is scaled by a runtime quantity (vscale).
+  bool isScalable() const { return this->UnivariateDim == ScalableDim; }
   /// A return value of true indicates we know at compile time that the number
   /// of elements (vscale * Min) is definitely even. However, returning false
   /// does not guarantee that the total number of elements is odd.
-  bool isKnownEven() const { return (MinVal & 0x1) == 0; }
-  ///@}
-
-  T getKnownMinValue() const { return MinVal; }
+  bool isKnownEven() const { return (getKnownMinValue() & 0x1) == 0; }
+  /// This function tells the caller whether the element count is known at
+  /// compile time to be a multiple of the scalar value RHS.
+  bool isKnownMultipleOf(ScalarTy RHS) const {
+    return getKnownMinValue() % RHS == 0;
+  }
 
   // Return the minimum value with the assumption that the count is exact.
   // Use in places where a scalable count doesn't make sense (e.g. non-vector
   // types, or vectors in backends which don't support scalable vectors).
-  T getFixedValue() const {
-    assert(!IsScalable &&
+  ScalarTy getFixedValue() const {
+    assert(!isScalable() &&
            "Request for a fixed element count on a scalable object");
-    return MinVal;
-  }
-
-  bool isScalable() const { return IsScalable; }
-
-  bool operator==(const PolySize &RHS) const {
-    return MinVal == RHS.MinVal && IsScalable == RHS.IsScalable;
+    return getKnownMinValue();
   }
 
-  bool operator!=(const PolySize &RHS) const { return !(*this == RHS); }
-
   // For some cases, size ordering between scalable and fixed size types cannot
   // be determined at compile time, so such comparisons aren't allowed.
   //
@@ -88,55 +306,30 @@
   // All the functions below make use of the fact vscale is always >= 1, which
   // means that <vscale x 4 x i32> is guaranteed to be >= <4 x i32>, etc.
 
-  static bool isKnownLT(const PolySize &LHS, const PolySize &RHS) {
-    if (!LHS.IsScalable || RHS.IsScalable)
-      return LHS.MinVal < RHS.MinVal;
-
-    // LHS.IsScalable = true, RHS.IsScalable = false
+  static bool isKnownLT(const LinearPolySize &LHS, const LinearPolySize &RHS) {
+    if (!LHS.isScalable() || RHS.isScalable())
+      return LHS.getKnownMinValue() < RHS.getKnownMinValue();
     return false;
   }
 
-  static bool isKnownGT(const PolySize &LHS, const PolySize &RHS) {
-    if (LHS.IsScalable || !RHS.IsScalable)
-      return LHS.MinVal > RHS.MinVal;
-
-    // LHS.IsScalable = false, RHS.IsScalable = true
+  static bool isKnownGT(const LinearPolySize &LHS, const LinearPolySize &RHS) {
+    if (LHS.isScalable() || !RHS.isScalable())
+      return LHS.getKnownMinValue() > RHS.getKnownMinValue();
     return false;
   }
 
-  static bool isKnownLE(const PolySize &LHS, const PolySize &RHS) {
-    if (!LHS.IsScalable || RHS.IsScalable)
-      return LHS.MinVal <= RHS.MinVal;
-
-    // LHS.IsScalable = true, RHS.IsScalable = false
+  static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS) {
+    if (!LHS.isScalable() || RHS.isScalable())
+      return LHS.getKnownMinValue() <= RHS.getKnownMinValue();
     return false;
   }
 
-  static bool isKnownGE(const PolySize &LHS, const PolySize &RHS) {
-    if (LHS.IsScalable || !RHS.IsScalable)
-      return LHS.MinVal >= RHS.MinVal;
-
-    // LHS.IsScalable = false, RHS.IsScalable = true
+  static bool isKnownGE(const LinearPolySize &LHS, const LinearPolySize &RHS) {
+    if (LHS.isScalable() || !RHS.isScalable())
+      return LHS.getKnownMinValue() >= RHS.getKnownMinValue();
     return false;
   }
 
-  PolySize operator*(T RHS) { return {MinVal * RHS, IsScalable}; }
-
-  PolySize &operator*=(T RHS) {
-    MinVal *= RHS;
-    return *this;
-  }
-
-  friend PolySize operator-(const PolySize &LHS, const PolySize &RHS) {
-    assert(LHS.IsScalable == RHS.IsScalable &&
-           "Arithmetic using mixed scalable and fixed types");
-    return {LHS.MinVal - RHS.MinVal, LHS.IsScalable};
-  }
-
-  /// This function tells the caller whether the element count is known at
-  /// compile time to be a multiple of the scalar value RHS.
-  bool isKnownMultipleOf(T RHS) const { return MinVal % RHS == 0; }
-
   /// We do not provide the '/' operator here because division for polynomial
   /// types does not work in the same way as for normal integer types. We can
   /// only divide the minimum value (or coefficient) by RHS, which is not the
@@ -145,72 +338,79 @@
   /// The caller is recommended to use this function in combination with
   /// isKnownMultipleOf(RHS), which lets the caller know if it's possible to
   /// perform a lossless divide by RHS.
-  PolySize divideCoefficientBy(T RHS) const {
-    return PolySize(MinVal / RHS, IsScalable);
+  LeafTy divideCoefficientBy(ScalarTy RHS) const {
+    return static_cast<LeafTy>(
+        LinearPolySize::get(getKnownMinValue() / RHS, isScalable()));
   }
 
-  PolySize coefficientNextPowerOf2() const {
-    return PolySize(static_cast<T>(llvm::NextPowerOf2(MinVal)), IsScalable);
+  LeafTy coefficientNextPowerOf2() const {
+    return static_cast<LeafTy>(LinearPolySize::get(
+        static_cast<ScalarTy>(llvm::NextPowerOf2(getKnownMinValue())),
+        isScalable()));
   }
 
   /// Printing function.
   void print(raw_ostream &OS) const {
-    if (IsScalable)
+    if (isScalable())
       OS << "vscale x ";
-    OS << MinVal;
+    OS << getKnownMinValue();
   }
 };
 
-/// Stream operator function for `PolySize`.
-template <typename T>
-inline raw_ostream &operator<<(raw_ostream &OS, const PolySize<T> &PS) {
-  PS.print(OS);
-  return OS;
-}
+class ElementCount;
+template <> struct LinearPolyBaseTypeTraits<ElementCount> {
+  using ScalarTy = unsigned;
+  static constexpr unsigned Dimensions = 2;
+};
 
-class ElementCount : public PolySize<unsigned> {
+class ElementCount : public LinearPolySize<ElementCount> {
 public:
-
-  constexpr ElementCount(PolySize<unsigned> V) : PolySize(V) {}
+  ElementCount(const LinearPolySize<ElementCount> &V) : LinearPolySize(V) {}
 
   /// Counting predicates.
   ///
-  /// Notice that MinVal = 1 and IsScalable = true is considered more than
-  /// one element.
-  ///
-  ///@{ No elements..
+  ///@{ Number of elements..
   /// Exactly one element.
-  bool isScalar() const { return !IsScalable && MinVal == 1; }
+  bool isScalar() const { return !isScalable() && getKnownMinValue() == 1; }
   /// One or more elements.
-  bool isVector() const { return (IsScalable && MinVal != 0) || MinVal > 1; }
+  bool isVector() const {
+    return (isScalable() && getKnownMinValue() != 0) || getKnownMinValue() > 1;
+  }
   ///@}
 };
 
-// This class is used to represent the size of types. If the type is of fixed
+class TypeSize;
+template <> struct LinearPolyBaseTypeTraits<TypeSize> {
+  using ScalarTy = uint64_t;
+  static constexpr unsigned Dimensions = 2;
+};
+
+// TODO: Most functionality in this class will gradually be phased out
+// so it will resemble LinearPolySize as much as possible.
+//
+// TypeSize is used to represent the size of types. If the type is of fixed
 // size, it will represent the exact size. If the type is a scalable vector,
 // it will represent the known minimum size.
-class TypeSize : public PolySize<uint64_t> {
+class TypeSize : public LinearPolySize<TypeSize> {
 public:
-  constexpr TypeSize(PolySize<uint64_t> V) : PolySize(V) {}
+  TypeSize(const LinearPolySize<TypeSize> &V) : LinearPolySize(V) {}
+  TypeSize(ScalarTy MinVal, bool IsScalable)
+      : LinearPolySize(LinearPolySize::get(MinVal, IsScalable)) {}
 
-  constexpr TypeSize(uint64_t MinVal, bool IsScalable)
-      : PolySize(MinVal, IsScalable) {}
+  static TypeSize Fixed(ScalarTy MinVal) { return TypeSize(MinVal, false); }
+  static TypeSize Scalable(ScalarTy MinVal) { return TypeSize(MinVal, true); }
 
-  static constexpr TypeSize Fixed(uint64_t MinVal) {
-    return TypeSize(MinVal, false);
-  }
-  static constexpr TypeSize Scalable(uint64_t MinVal) {
-    return TypeSize(MinVal, true);
-  }
+  ScalarTy getFixedSize() const { return getFixedValue(); }
+  ScalarTy getKnownMinSize() const { return getKnownMinValue(); }
 
-  uint64_t getFixedSize() const { return getFixedValue(); }
-  uint64_t getKnownMinSize() const { return getKnownMinValue(); }
+  // The comparison operators are in the process of being phased out
+  // in favour of isKnownLT/isKnownLE of its parent class.
 
   friend bool operator<(const TypeSize &LHS, const TypeSize &RHS) {
-    assert(LHS.IsScalable == RHS.IsScalable &&
+    assert(LHS.isScalable() == RHS.isScalable() &&
            "Ordering comparison of scalable and fixed types");
 
-    return LHS.MinVal < RHS.MinVal;
+    return LHS.getKnownMinValue() < RHS.getKnownMinValue();
   }
 
   friend bool operator>(const TypeSize &LHS, const TypeSize &RHS) {
@@ -221,29 +421,15 @@
     return !(RHS < LHS);
   }
 
-  friend bool operator>=(const TypeSize &LHS, const TypeSize& RHS) {
+  friend bool operator>=(const TypeSize &LHS, const TypeSize &RHS) {
     return !(LHS < RHS);
   }
 
-  TypeSize &operator-=(TypeSize RHS) {
-    assert(IsScalable == RHS.IsScalable &&
-           "Subtraction using mixed scalable and fixed types");
-    MinVal -= RHS.MinVal;
-    return *this;
-  }
-
-  TypeSize &operator+=(TypeSize RHS) {
-    assert(IsScalable == RHS.IsScalable &&
-           "Addition using mixed scalable and fixed types");
-    MinVal += RHS.MinVal;
-    return *this;
-  }
-
-  friend TypeSize operator-(const TypeSize &LHS, const TypeSize &RHS) {
-    assert(LHS.IsScalable == RHS.IsScalable &&
-           "Arithmetic using mixed scalable and fixed types");
-    return {LHS.MinVal - RHS.MinVal, LHS.IsScalable};
-  }
+  // All code for this class below this point is needed because of the
+  // temporary implicit conversion to uint64_t. The operator overloads are
+  // needed because otherwise the conversion of the parent class UnivariateLinearPolyBase
+  // -> TypeSize is ambiguous.
+  // TODO: Remove the implicit conversion.
 
   // Casts to a uint64_t if this is a fixed-width size.
   //
@@ -263,7 +449,7 @@
   //     else
   //       bail out early for scalable vectors and use getFixedValue()
   //   }
-  operator uint64_t() const {
+  operator ScalarTy() const {
 #ifdef STRICT_FIXED_SIZE_VECTORS
     return getFixedValue();
 #else
@@ -275,35 +461,35 @@
 #endif
   }
 
-  // Convenience operators to obtain relative sizes independently of
-  // the scalable flag.
-  TypeSize operator*(unsigned RHS) const { return {MinVal * RHS, IsScalable}; }
-
-  friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) {
-    return {LHS * RHS.MinVal, RHS.IsScalable};
+  // Additional operators needed to avoid ambiguous parses
+  // because of the implicit conversion hack.
+  friend TypeSize operator*(const TypeSize &LHS, const int RHS) {
+    return LHS * (ScalarTy)RHS;
   }
-
-  // Additional convenience operators needed to avoid ambiguous parses.
-  // TODO: Make uint64_t the default operator?
-  TypeSize operator*(uint64_t RHS) const { return {MinVal * RHS, IsScalable}; }
-
-  TypeSize operator*(int RHS) const { return {MinVal * RHS, IsScalable}; }
-
-  TypeSize operator*(int64_t RHS) const { return {MinVal * RHS, IsScalable}; }
-
-  friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) {
-    return {LHS * RHS.MinVal, RHS.IsScalable};
+  friend TypeSize operator*(const TypeSize &LHS, const unsigned RHS) {
+    return LHS * (ScalarTy)RHS;
+  }
+  friend TypeSize operator*(const TypeSize &LHS, const int64_t RHS) {
+    return LHS * (ScalarTy)RHS;
   }
-
   friend TypeSize operator*(const int LHS, const TypeSize &RHS) {
-    return {LHS * RHS.MinVal, RHS.IsScalable};
+    return RHS * LHS;
+  }
+  friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) {
+    return RHS * LHS;
   }
-
   friend TypeSize operator*(const int64_t LHS, const TypeSize &RHS) {
-    return {LHS * RHS.MinVal, RHS.IsScalable};
+    return RHS * LHS;
+  }
+  friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) {
+    return RHS * LHS;
   }
 };
 
+//===----------------------------------------------------------------------===//
+// Utilities
+//===----------------------------------------------------------------------===//
+
 /// Returns a TypeSize with a known minimum size that is the next integer
 /// (mod 2**64) that is greater than or equal to \p Value and is a multiple
 /// of \p Align. \p Align must be non-zero.
@@ -315,6 +501,15 @@
           Size.isScalable()};
 }
 
+/// Stream operator function for `LinearPolySize`.
+template <typename LeafTy>
+inline raw_ostream &operator<<(raw_ostream &OS,
+                               const LinearPolySize<LeafTy> &PS) {
+  PS.print(OS);
+  return OS;
+}
+
+template <typename T> struct DenseMapInfo;
 template <> struct DenseMapInfo<ElementCount> {
   static inline ElementCount getEmptyKey() {
     return ElementCount::getScalable(~0U);
@@ -322,7 +517,7 @@
   static inline ElementCount getTombstoneKey() {
     return ElementCount::getFixed(~0U - 1);
   }
-  static unsigned getHashValue(const ElementCount& EltCnt) {
+  static unsigned getHashValue(const ElementCount &EltCnt) {
     unsigned HashVal = EltCnt.getKnownMinValue() * 37U;
     if (EltCnt.isScalable())
       return (HashVal - 1U);
@@ -330,7 +525,7 @@
     return HashVal;
   }
 
-  static bool isEqual(const ElementCount& LHS, const ElementCount& RHS) {
+  static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) {
     return LHS == RHS;
   }
 };
Index: llvm/unittests/Support/CMakeLists.txt
===================================================================
--- llvm/unittests/Support/CMakeLists.txt
+++ llvm/unittests/Support/CMakeLists.txt
@@ -44,6 +44,7 @@
   JSONTest.cpp
   KnownBitsTest.cpp
   LEB128Test.cpp
+  LinearPolyBaseTest.cpp
   LineIteratorTest.cpp
   LockFileManagerTest.cpp
   MatchersTest.cpp
Index: llvm/unittests/Support/LinearPolyBaseTest.cpp
===================================================================
--- /dev/null
+++ llvm/unittests/Support/LinearPolyBaseTest.cpp
@@ -0,0 +1,164 @@
+//===- TestPoly3D.cpp - Poly3D unit tests------------------------===//
+//
+// 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 "llvm/Support/TypeSize.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+class Poly3D;
+template <> struct llvm::LinearPolyBaseTypeTraits<Poly3D> {
+  using ScalarTy = int64_t;
+  static const unsigned Dimensions = 3;
+};
+
+using Poly3DBase = LinearPolyBase<Poly3D>;
+class Poly3D : public Poly3DBase {
+public:
+  using ScalarTy = Poly3DBase::ScalarTy;
+  Poly3D(ScalarTy x, ScalarTy y, ScalarTy z) : Poly3DBase({x, y, z}) {}
+  Poly3D(const Poly3DBase &Convert) : Poly3DBase(Convert) {}
+};
+
+TEST(LinearPolyBase, Poly3D_isZero) {
+  EXPECT_TRUE(Poly3D(0, 0, 0).isZero());
+  EXPECT_TRUE(Poly3D(0, 0, 1).isNonZero());
+  EXPECT_TRUE(Poly3D(0, 0, 1));
+}
+
+TEST(LinearPolyBase, Poly3D_Equality) {
+  EXPECT_EQ(Poly3D(1, 2, 3), Poly3D(1, 2, 3));
+  EXPECT_NE(Poly3D(1, 2, 3), Poly3D(1, 2, 4));
+}
+
+TEST(LinearPolyBase, Poly3D_GetValue) {
+  EXPECT_EQ(Poly3D(1, 2, 3).getValue(0), 1);
+  EXPECT_EQ(Poly3D(1, 2, 3).getValue(1), 2);
+  EXPECT_EQ(Poly3D(1, 2, 3).getValue(2), 3);
+}
+
+TEST(LinearPolyBase, Poly3D_Add) {
+  // Test operator+
+  EXPECT_EQ(Poly3D(42, 0, 0) + Poly3D(0, 42, 0) + Poly3D(0, 0, 42),
+            Poly3D(42, 42, 42));
+
+  // Test operator+=
+  Poly3D X(42, 0, 0);
+  X += Poly3D(0, 42, 0);
+  X += Poly3D(0, 0, 42);
+  EXPECT_EQ(X, Poly3D(42, 42, 42));
+}
+
+TEST(LinearPolyBase, Poly3D_Sub) {
+  // Test operator-
+  EXPECT_EQ(Poly3D(42, 42, 42) - Poly3D(42, 0, 0) - Poly3D(0, 42, 0) -
+                Poly3D(0, 0, 42),
+            Poly3D(0, 0, 0));
+
+  // Test operator-=
+  Poly3D X(42, 42, 42);
+  X -= Poly3D(42, 0, 0);
+  X -= Poly3D(0, 42, 0);
+  X -= Poly3D(0, 0, 42);
+  EXPECT_EQ(X, Poly3D(0, 0, 0));
+}
+
+TEST(LinearPolyBase, Poly3D_Scale) {
+  // Test operator*
+  EXPECT_EQ(Poly3D(1, 2, 4) * 2, Poly3D(2, 4, 8));
+  EXPECT_EQ(Poly3D(1, 2, 4) * -2, Poly3D(-2, -4, -8));
+}
+
+TEST(LinearPolyBase, Poly3D_Invert) {
+  // Test operator-
+  EXPECT_EQ(-Poly3D(2, 4, 8), Poly3D(-2, -4, -8));
+}
+
+class Univariate3D;
+template <> struct llvm::LinearPolyBaseTypeTraits<Univariate3D> {
+  using ScalarTy = int64_t;
+  static const unsigned Dimensions = 3;
+};
+
+using Univariate3DBase = UnivariateLinearPolyBase<Univariate3D>;
+class Univariate3D : public Univariate3DBase {
+public:
+  using ScalarTy = Univariate3DBase::ScalarTy;
+  Univariate3D(ScalarTy x, unsigned Dim) : Univariate3DBase(x, Dim) {}
+  Univariate3D(const Univariate3DBase &Convert) : Univariate3DBase(Convert) {}
+};
+
+TEST(UnivariateLinearPolyBase, Univariate3D_isZero) {
+  EXPECT_TRUE(Univariate3D(0, 0).isZero());
+  EXPECT_TRUE(Univariate3D(0, 1).isZero());
+  EXPECT_TRUE(Univariate3D(0, 2).isZero());
+  EXPECT_TRUE(Univariate3D(1, 0).isNonZero());
+  EXPECT_TRUE(Univariate3D(1, 1).isNonZero());
+  EXPECT_TRUE(Univariate3D(1, 2).isNonZero());
+  EXPECT_TRUE(Univariate3D(1, 0));
+}
+
+TEST(UnivariateLinearPolyBase, Univariate3D_Equality) {
+  EXPECT_EQ(Univariate3D(1, 0), Univariate3D(1, 0));
+  EXPECT_NE(Univariate3D(1, 0), Univariate3D(1, 2));
+  EXPECT_NE(Univariate3D(1, 0), Univariate3D(1, 1));
+  EXPECT_NE(Univariate3D(1, 0), Univariate3D(2, 0));
+  EXPECT_NE(Univariate3D(1, 0), Univariate3D(0, 0));
+}
+
+TEST(UnivariateLinearPolyBase, Univariate3D_GetValue) {
+  EXPECT_EQ(Univariate3D(42, 0).getValue(0), 42);
+  EXPECT_EQ(Univariate3D(42, 0).getValue(1), 0);
+  EXPECT_EQ(Univariate3D(42, 0).getValue(2), 0);
+
+  EXPECT_EQ(Univariate3D(42, 1).getValue(0), 0);
+  EXPECT_EQ(Univariate3D(42, 1).getValue(1), 42);
+  EXPECT_EQ(Univariate3D(42, 1).getValue(2), 0);
+
+  EXPECT_EQ(Univariate3D(42, 0).getValue(), 42);
+  EXPECT_EQ(Univariate3D(42, 1).getValue(), 42);
+}
+
+TEST(UnivariateLinearPolyBase, Univariate3D_Add) {
+  // Test operator+
+  EXPECT_EQ(Univariate3D(42, 0) + Univariate3D(42, 0), Univariate3D(84, 0));
+  EXPECT_EQ(Univariate3D(42, 1) + Univariate3D(42, 1), Univariate3D(84, 1));
+  EXPECT_DEBUG_DEATH(Univariate3D(42, 0) + Univariate3D(42, 1),
+                     "Invalid dimensions");
+
+  // Test operator+=
+  Univariate3D X(42, 0);
+  X += Univariate3D(42, 0);
+  EXPECT_EQ(X, Univariate3D(84, 0));
+}
+
+TEST(UnivariateLinearPolyBase, Univariate3D_Sub) {
+  // Test operator+
+  EXPECT_EQ(Univariate3D(84, 0) - Univariate3D(42, 0), Univariate3D(42, 0));
+  EXPECT_EQ(Univariate3D(84, 1) - Univariate3D(42, 1), Univariate3D(42, 1));
+  EXPECT_DEBUG_DEATH(Univariate3D(84, 0) - Univariate3D(42, 1),
+                     "Invalid dimensions");
+
+  // Test operator+=
+  Univariate3D X(84, 0);
+  X -= Univariate3D(42, 0);
+  EXPECT_EQ(X, Univariate3D(42, 0));
+}
+
+TEST(UnivariateLinearPolyBase, Univariate3D_Scale) {
+  // Test operator*
+  EXPECT_EQ(Univariate3D(4, 0) * 2, Univariate3D(8, 0));
+  EXPECT_EQ(Univariate3D(4, 1) * -2, Univariate3D(-8, 1));
+}
+
+TEST(UnivariateLinearPolyBase, Univariate3D_Invert) {
+  // Test operator-
+  EXPECT_EQ(-Univariate3D(4, 0), Univariate3D(-4, 0));
+  EXPECT_EQ(-Univariate3D(4, 1), Univariate3D(-4, 1));
+}
+