[NFCI] Add StackOffset class and base classes for ElementCount, TypeSize.

[sdesmalen]

Summary

This patch adds a linear polynomial base class, called LinearPolyBase, which
serves as a base class for StackOffset. It tries to represent a linear
polynomial like:

c0 * scale0 + c1 * scale1 + ... + cK * scaleK

where the scale is implicit, meaning that only the coefficients are
encoded.

This patch also adds a univariate linear polynomial, which serves as
a base class for ElementCount and TypeSize. This tries to represent a
linear polynomial where only one dimension can be set at any one time,
i.e. a TypeSize is either fixed-sized, or scalable-sized, but cannot be
a combination of the two.

class LinearPolyBase
   ^
   |
   +---- class StackOffset  (dimensions = 2 (fixed/scalable), type = int64_t)

class UnivariateLinearPolyBase
   |
   |
   +---- class LinearPolySize (dimensions = 2 (fixed/scalable))
                ^
                |
                +-------- class ElementCount  (type = unsigned)
                |
                |
                +-------- class TypeSize      (type = uint64_t)

[ctetreau]

This isn't really a true polynomial because it doesn't support multiplication of two terms: 2x * 2x = 4x^2

If what we have here is all we need, then I think it's fine (having not actually code reviewed the implementation at the time of this writing), but we should call it like it is, and ideally implement it in such a way that it would be straightforward to implement a true polynomial.

[sdesmalen]

In D88982#2317443, @ctetreau wrote:

This isn't really a true polynomial because it doesn't support multiplication of two terms: 2x * 2x = 4x^2

If what we have here is all we need, then I think it's fine (having not actually code reviewed the implementation at the time of this writing), but we should call it like it is, and ideally implement it in such a way that it would be straightforward to implement a true polynomial.

Are you suggesting rename PolyBase or just to remove the term 'polynomial' from the commit message and any of the comments?

[ctetreau]

In D88982#2317488, @sdesmalen wrote:

Are you suggesting rename PolyBase or just to remove the term 'polynomial' from the commit message and any of the comments?

I'm suggesting a rename. According to wikipedia, a polynomial of first degree is called a linear polynomial. So, I propose the following simplified hierarchy:

LinearPolyBase<Type, Dimensions, IsUnivariate>
   ^   
   |   
   +---- StackOffset : LinearPolyBase<int64_t, 2, false>
   ^
   |   
   +---- PolySize : LinearPolyBase<Type, 2, true>
                ^   
                |   
                +------------- ElementCount (typedef with Type=unsigned)
                |   
                +------------- TypeSize (subclass with Type=uint64_t)

If we do this, and don't define operator* with another linear polynomial on the right, then we should be good to go. I don't think MixedPolyBase2D bought us anything, all the new things you added were "scalable" specific anyway. Similarly, for SinglePolyBase2D: might as well just let it be a "scalable size" IMO.

[ctetreau]

llvm/include/llvm/Support/TypeSize.h

137–152

NIT: might as well use std::array

140

NIT: Nomenclature: suggest changing to IsUnivariate to match the terminology of the mathematical concept

143

NIT: it would be more immediately obvious what this is if you used std::numeric_limits<unsigned>::max()

181

I don't think the call to verify() is necessary in any of the arithmetic operators. Just assert that RHS and LHS have the same value set for ExclusiveDim.

You could even special case:

if (DimIsExclusive) {
   Coefficients[ExclusiveDim] += RHS.Coefficients[ExclusiveDim];
}
else {
   ...
}

[sdesmalen]

• Renamed PolyBase -> LinearPolyBase, DimIsExclusive -> IsUnivariate, etc.
• Removed verify() method.
• Replaced regular array with std::array.
• Changed name of new StackOffset class in TypeSize.h to NewStackOffset, so not to clash with the one defined in AArch64StackOffset.h. This is renamed to StackOffset in D88983 when it removes AArch64StackOffset.h entirely.
• Moved TestStackOffset.cpp from D88983 to this patch.
• Updated commit message.

[sdesmalen]

• Rebased patch.
• Added class LinearPolyBaseOperators which provides a set of overloaded operators for derived classes.
• Made ElementCount a deriving class, because it needs 'isScalar' and 'isVector' methods which cannot be part of its parent class.

[david-arm]

llvm/include/llvm/Support/TypeSize.h

135

Can you remove the need for ScalarTy by having Ty provide the scalar type? i.e. Ty::ScalarTy, where ScalarTy would be a typedef or something inside LinearPolyBase?

Instead of using multiple inheritance to get the operators, is it not possible to simply have the operators outside of any class? I think C++ allows you to do this provided the operators are friends of the relevant classes, i.e. just have

template <Ty>
LinearPolyBase<Ty> operator+(const LinearPolyBase<Ty> LHS, const LinearPolyBase<Ty> RHS) {

for (unsigned I = 0; I < Dimensions; ++I)
  LHS.Coefficients[I] -= RHS.Coefficients[I];
return LHS;

}

although I realise the example above only works if you have a simplified LinearPolyBase that assumes 2 dimensions, rather than the 3 template parameters you currently have for LinearPolyBase.

177

Do we actually need to support this right now? I just wonder if we can simplify things by just assuming it's always univariate for now. I guess I'm just worried that we're trying to provide theoretical support for something with no proof as yet that it's needed. We're always going to be targeting one backend, so when switching backends vscale will mean whatever is appropriate for the given backend. I think this code is trying to support a single backend having multiple vscales, unless I've misunderstood something?

Also, what happens when the user specifies 3 dimensions and IsUnivariate=true? I guess this is technically allowed, but looks a little odd that's all.

This is just a suggestion, but I wonder if the code might be made simpler by always assuming coefficient 0 is unscaled. Then 2 dimensions always implies both univariate and that coefficient 1 is scaled? By definition, 3 dimensions automatically implies IsUnivariate=false too I think? In this case you may actually only need two template parameters. Also, if we assume for now we're always dealing with exactly two dimensions then the enable_if stuff goes away too as then you only need one two-arg constructor.

[sdesmalen]

llvm/include/llvm/Support/TypeSize.h

135

Instead of using multiple inheritance to get the operators, is it not possible to simply have the operators outside of any class

That is kind of what this class tries to do. It defines the functions as friend functions, where it takes the result/operand types from the derived class, like TypeSize, ElementCount or StackOffset.

The problem with using inheritance for the operators is that it inherits the parent's operators, which return the parent class' type. That requires implicit conversion of parent -> derived class. By inheriting from this class like this:

class ElementCount : public LinearPolyBase<...>,
                     public LinearPolyBaseOperators<ElementCount, ...> {
};

it will automatically instantiate those operators for the derived class.

177

Do we actually need to support this right now? I just wonder if we can simplify things by just assuming it's always univariate for now.

We need this for StackOffset, which has IsUnivariate = false, because it needs to support a combination of fixed and scalable elements.

I think this code is trying to support a single backend having multiple vscales, unless I've misunderstood something?

I've made it generic enough in case this is needed in the future, mostly because it didn't really make things more complicated. I guess we could fix the Dimensions to 2, and remove this template operand from the class and explicitly name these dimensions 'Fixed' and 'Scalable', although I'm not sure if that would actually simplify these classes much.

Also, what happens when the user specifies 3 dimensions and IsUnivariate=true? I guess this is technically allowed, but looks a little odd that's all.
This is just a suggestion, but I wonder if the code might be made simpler by always assuming coefficient 0 is unscaled. Then 2 dimensions always implies both univariate and that coefficient 1 is scaled? By definition, 3 dimensions automatically implies IsUnivariate=false too I think? In this case you may actually only need two template parameters

The dimensions don't have a meaning in this class, it's just a representation for: c0 * scale0 + c1 * scale1 + ... + cK * scaleK. This abstract class could represent a K dimensionsal linear polynomial, where IsUnivariate would ensure that only one of {c0, c1, ..., ck} is non-zero.

Also, if we assume for now we're always dealing with exactly two dimensions then the enable_if stuff goes away too as then you only need one two-arg constructor

The enable_if is there to distinguish constructors for the Univariate and non-Univariate cases. i.e. If only one dimension is allowed to be set, you call it with (cK, #dimK), otherwise you call it with ({c0, c1, ..., cK}).

[ctetreau]

@sdesmalen I'm generally ok with this approach. This patch is pretty complicated, so I haven't had the time to fully digest it and decide if it's actually correct. I plan to try to find time to do this soon, but I'd feel more comfortable if others took a look as well.

llvm/include/llvm/Support/TypeSize.h

177

I like the template parameter for the number of different variables, and would prefer that we didn't fix it to 2. I think it doesn't really increase the complexity, and makes supporting more in a hypothetical future where some target has multiple vscale like things much easier. It is my personal opinion that N+1 template parameters aren't more complex than N template parameters unless N is zero.

[ctetreau]

llvm/include/llvm/Support/TypeSize.h

135

Is it ever valid for the operator to have a different scalar type than the polynomial?

If not, then I agree with David that LinearPolyBase should publicly expose a using ScalarType = T, and that this type should only 1 template parameter that is the polynomial type.

It might also be nice to do some type_traits magic to static_assert that the polynomial type actually inherits from LinearPolyBase so the user doesn't get 20 pages of template garbage if they mess it up.

177

NIT: add static_assert that Dimensions is not unsigned max

254

why "NewStackOffset"?

255

Shouldn't the first template parameter be NewStackOffset?

271

What's the point of this? NewStackOffset is already basically a pair of int64_t.

Also, the user must read the implementation to know which member of the pair is the fixed coefficient and which is the scalable one. At the very least, this should be documented.

286

If we name these dims, we can just use them instead of mapping bool -> unsigned

287–288

293–294

296

302

llvm/unittests/Support/StackOffsetTest.cpp

1 ↗

(On Diff #297619)

We should probably just write unit tests for LinearPolyBase, and get rid of tests for ElementCount, TypeSize, and StackOffset unless they test actual new features.

[sdesmalen]

• Removed need for LinearPolyBaseOperators. The code now passes the derived leaf type (i.e. ElementCount/TypeSize) directly to its parent classes and the operators in the base class are now defined to take/return the leaf type.
• The scalar type is no longer passed separately, but derived from the Leaf type using a type traits class.
• Added new tests based directly on LinearPolyBase.

[sdesmalen]

Thanks for the feedback @ctetreau!

llvm/include/llvm/Support/TypeSize.h

135

Is it ever valid for the operator to have a different scalar type than the polynomial?

It is not.

If not, then I agree with David that LinearPolyBase should publicly expose a using ScalarType = T, and that this type should only 1 template parameter that is the polynomial type.

It might also be nice to do some type_traits magic to static_assert that the polynomial type actually inherits from LinearPolyBase so the user doesn't get 20 pages of template garbage if they mess it up.

Okay I've changed things a bit in the latest update, by using a Traits class to get the ScalarType, and passing the Leaf type (i.e. StackOffset/TypeSize/ElementCount) directly to the base class. That also rendered the LinearPolyBaseOperators class unnecessary, as this can now move directly into the base class.

I've also tried adding some static_assert(std::is_base_of<LinearPolyBase, LeafTy>), but that falls over because LeafTy is incomplete at the point where this is being evaluated.

254

That was to avoid a name clash with StackOffset defined in AArch64StackOffset.h when both that header and TypeSize.h are included. This got renamed back in D88983. But it's better to put this in a separate namespace, and remove only that namespace in D88983.

255

Yes. Not sure how this happened.

271

The NewStackOffset is indeed a pair, but it's not a std::pair, so I thought it would be nice to have this as convenience function. But it's probably better to remove this interface for now, as I don't use it in any of the follow-up patches.

286

That's a great suggestion, thanks!

[ctetreau]

llvm/include/llvm/Support/TypeSize.h

137–152

Couldn't we just require that any type used as LeafTy have a ScalarTy typedef?

252–255

Does this need to be inside the NewStackOffset namespace? I believe that you are forward declaring llvm::StackOffset and then creating the type traits for it, not llvm::NewStackOffset::StackOffset

[sdesmalen]

• Fixed namespace for StackOffset traits.
• Noticed that StackOffset was still using int64_t instead of it's ScalarTy, so fixed it.
• Changed instance of std::all_of -> llvm::all_of

[sdesmalen]

llvm/include/llvm/Support/TypeSize.h

137–152

When I try that, I get:

error: invalid use of incomplete type 'class llvm::StackOffset'
   55 |   using SomeOtherTy = typename LeafTy::SomeTy;
      |         ^~~~~~~~~~~

252–255

Good catch! I'm not sure why this still built. I can't move the specialization into the NewStackOffset namespace, as this needs to happen in the same namespace as it's declaration, but I can move the forward declaration of StackOffset into a namespace, and specify the traits for NewStackOffset::StackOffset.

[georges]

llvm/include/llvm/Support/TypeSize.h

165–166

Not a suggestion, but just an observation that we're passing some arguments to the class via template parameters and others via the traits object. Seems inconsistent?

176–183

Is it worth specializing this struct template for IsUnivariate=true/false, since with the number of enable_if's scattered around they begin to look like quite different classes? It also seems a bit wasteful to be allocating Dimensions elements when all but one of them will be zero in the Univariate case?

234

nit: I think you can use the _v/_t versions of these functions here and elsewhere since we're in C++14 now, e.g. std::enable_if_t<std::is_signed_v<U>, LeafTy>.

[ctetreau]

llvm/include/llvm/Support/TypeSize.h

241–244

Out of bounds array access.

[ctetreau]

llvm/include/llvm/Support/TypeSize.h

137–152

I played around with it for a bit today, and I was unable to make it any nicer.

[sdesmalen]

llvm/include/llvm/Support/TypeSize.h

176–183

@ctetreau do you have any thoughts on this? I guess I could split this up and end up with a two base classes, as I agree with @georges that for >2 dimensions the code isn't optimal. By having two base classes, the univariate case can be optimized. The downside is some duplication, but it would avoid the need for enable_if and probably simplify the code.

241–244

Eek, good spot!

[ctetreau]

llvm/include/llvm/Support/TypeSize.h

176–183

I'm not so much worried about wasted space because Dimensions is likely to be low.

However, my general feeling is that this class getting way too fancy with the template metaprogramming. I wasn't going to complain about it, but since you're asking I think it would be more straightforward if they were separate classes.

I've also wondered on more than on occasion if we ought to just use a linear algebra lib for this. This class smells a lot like a vector to me...

[sdesmalen]

• Separated out the base classes, one specialized for StackOffset and another specialized for LinearPolySize.
• Moved dimensions to Traits class.
• Use enable_if_t instead of enable_if

[sdesmalen]

Okay, I have addressed all comments. Specializing the two base classes for Mixed and Univariate cases and moving the dimension to the Traits class improves the code quite a bit.
Let me know what you think!

llvm/include/llvm/Support/TypeSize.h

176–183

Using a linear algebra lib is probably a bit overkill here as the few supported operations are simple enough to implement. Unless there is already something in LLVM for this?

[georges]

llvm/include/llvm/Support/TypeSize.h

180

worth an assert that UniveriateDim is in range?

[georges]

Other than the nit, LGTM. I'll let others have a look and accept.

[ctetreau]

Looks good to me once you add that assert.

llvm/include/llvm/Support/TypeSize.h

176–183

Yeah, that was my thought too, which is why I didn't actually suggest it. I'm surprised we don't have a linear algebra lib already (either homegrown or not) though. Seems like it'd be useful for doing things like constexpr matrix multiplications.

180

I think this would be a useful assert

[sdesmalen]

Added assert.

[sdesmalen]

llvm/include/llvm/Support/TypeSize.h

180

Agreed, good catch!

[david-arm]

LGTM and a lot tidier now, provided you're also happy with this @ctetreau?

[ctetreau]

Yeah, I think this is good to go

[sdesmalen]

Thanks for the reviews and great feedback, I feel like the patch has much improved since its first revision!

llvm/include/llvm/Support/TypeSize.h

 // which may be scalable vectors. It provides convenience operators so that
 // it can be used in much the same way as a single scalar value.
 //
 //===----------------------------------------------------------------------===//
 
 #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;
+};
 
-// 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 {
+namespace NewStackOffset {
+
+/// 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); }
+};
+
+} // end namespace NewStackOffset
 
-  constexpr PolySize(T MinVal, bool IsScalable)
-      : MinVal(MinVal), IsScalable(IsScalable) {}
 
+//===----------------------------------------------------------------------===//
+// 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");
+
+protected:
+  ScalarTy Value;         // The value at the univeriate dimension.
+  unsigned UnivariateDim; // The univeriate dimension.
 
-  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};
+  UnivariateLinearPolyBase(ScalarTy &Val, unsigned UnivariateDim)
+      : Value(Val), UnivariateDim(UnivariateDim) {
+    assert(UnivariateDim < Dimensions && "Dimension out of range");
   }
 
-  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, const LeafTy &RHS) {
+    assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions");
+    LHS.Value -= RHS.Value;
+    return LHS;
+  }
+
+  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));
+  }
+  static LeafTy getNull() { return get(0, false); }
+
+  /// 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.
   //
   // e.g. <vscale x 2 x i16> could be bigger than <4 x i32> with a runtime
   // vscale >= 5, equal sized with a vscale of 4, and smaller with
   // a vscale <= 3.
   //
   // 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
   /// same as
   ///   (Min * Vscale) / RHS
   /// 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) {}
-
-  constexpr TypeSize(uint64_t MinVal, bool IsScalable)
-      : PolySize(MinVal, IsScalable) {}
-
-  static constexpr TypeSize Fixed(uint64_t MinVal) {
-    return TypeSize(MinVal, false);
-  }
-  static constexpr TypeSize Scalable(uint64_t MinVal) {
-    return TypeSize(MinVal, true);
-  }
-
-  uint64_t getFixedSize() const { return getFixedValue(); }
-  uint64_t getKnownMinSize() const { return getKnownMinValue(); }
-
-  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};
-  }
+  TypeSize(const LinearPolySize<TypeSize> &V) : LinearPolySize(V) {}
+  TypeSize(ScalarTy MinVal, bool IsScalable)
+      : LinearPolySize(LinearPolySize::get(MinVal, IsScalable)) {}
+
+  static TypeSize Fixed(ScalarTy MinVal) { return TypeSize(MinVal, false); }
+  static TypeSize Scalable(ScalarTy MinVal) { return TypeSize(MinVal, true); }
+
+  ScalarTy getFixedSize() const { return getFixedValue(); }
+  ScalarTy getKnownMinSize() const { return getKnownMinValue(); }
+
+  // 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.
   //
   // This interface is deprecated and will be removed in a future version
   // of LLVM in favour of upgrading uses that rely on this implicit conversion
   // to uint64_t. Calls to functions that return a TypeSize should use the
   // proper interfaces to TypeSize.
   // In practice this is mostly calls to MVT/EVT::getSizeInBits().
   //
   // To determine how to upgrade the code:
   //
   //   if (<algorithm works for both scalable and fixed-width vectors>)
   //     use getKnownMinValue()
   //   else if (<algorithm works only for fixed-width vectors>) {
   //     if <algorithm can be adapted for both scalable and fixed-width vectors>
   //       update the algorithm and use getKnownMinValue()
   //     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
     if (isScalable())
       WithColor::warning() << "Compiler has made implicit assumption that "
                               "TypeSize is not scalable. This may or may not "
                               "lead to broken code.\n";
     return getKnownMinValue();
 #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.
 ///
 /// Similar to the alignTo functions in MathExtras.h
 inline TypeSize alignTo(TypeSize Size, uint64_t Align) {
   assert(Align != 0u && "Align must be non-zero");
   return {(Size.getKnownMinValue() + Align - 1) / Align * Align,
           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);
   }
   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);
 
     return HashVal;
   }
 
-  static bool isEqual(const ElementCount& LHS, const ElementCount& RHS) {
+  static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) {
     return LHS == RHS;
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_TypeSize_H

llvm/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   FSUniqueIDTest.cpp
   GlobPatternTest.cpp
   Host.cpp
   IndexedAccessorTest.cpp
   ItaniumManglingCanonicalizerTest.cpp
   JSONTest.cpp
   KnownBitsTest.cpp
   LEB128Test.cpp
+  LinearPolyBaseTest.cpp
   LineIteratorTest.cpp
   LockFileManagerTest.cpp
   MatchersTest.cpp
   MD5Test.cpp
   ManagedStatic.cpp
   MathExtrasTest.cpp
   MemoryBufferRefTest.cpp
   MemoryBufferTest.cpp

llvm/unittests/Support/LinearPolyBaseTest.cpp

+//===- 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));
+}
+