This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by sdesmalen on Oct 7 2020, 10:03 AM.

Details

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)

Diff Detail

Event Timeline

sdesmalen created this revision.Oct 7 2020, 10:03 AM
Herald added projects: Restricted Project, Restricted Project. · View Herald Transcript
sdesmalen requested review of this revision.Oct 7 2020, 10:03 AM

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.

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?

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 added inline comments.Oct 7 2020, 2:27 PM
llvm/include/llvm/Support/TypeSize.h
34

NIT: might as well use std::array

40

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

42

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

64

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 updated this revision to Diff 297002.Oct 8 2020, 9:57 AM
sdesmalen marked 4 inline comments as done.
sdesmalen retitled this revision from [NFCI] Add PolyBase as base class for ElementCount, TypeSize and StackOffset. to [NFCI] Add LinearPolyBase as base class for ElementCount, TypeSize and StackOffset..
sdesmalen edited the summary of this revision. (Show Details)
  • 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.
  • 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.
sdesmalen edited the summary of this revision. (Show Details)Oct 12 2020, 10:03 AM
david-arm added inline comments.Oct 13 2020, 5:01 AM
llvm/include/llvm/Support/TypeSize.h
37

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.

79

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 added inline comments.Oct 13 2020, 7:18 AM
llvm/include/llvm/Support/TypeSize.h
37

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.

79

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}).

@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
79

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 added inline comments.Oct 21 2020, 10:16 AM
llvm/include/llvm/Support/TypeSize.h
37

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.

79

NIT: add static_assert that Dimensions is not unsigned max

160

why "NewStackOffset"?

161

Shouldn't the first template parameter be NewStackOffset?

177

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.

192

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

193–194
199–200
202
208
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 marked 6 inline comments as done.
  • 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.

Thanks for the feedback @ctetreau!

llvm/include/llvm/Support/TypeSize.h
37

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.

160

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.

161

Yes. Not sure how this happened.

177

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.

192

That's a great suggestion, thanks!

ctetreau added inline comments.Oct 22 2020, 2:46 PM
llvm/include/llvm/Support/TypeSize.h
34

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

158–161

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 updated this revision to Diff 300200.Oct 23 2020, 2:35 AM
sdesmalen marked 9 inline comments as done.
  • 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 added inline comments.Oct 23 2020, 2:49 AM
llvm/include/llvm/Support/TypeSize.h
34

When I try that, I get:

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

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 added inline comments.Oct 26 2020, 5:30 AM
llvm/include/llvm/Support/TypeSize.h
47–48

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?

56–67

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?

118

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 added inline comments.Oct 26 2020, 12:04 PM
llvm/include/llvm/Support/TypeSize.h
125–128

Out of bounds array access.

ctetreau added inline comments.Oct 26 2020, 1:00 PM
llvm/include/llvm/Support/TypeSize.h
34

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

sdesmalen added inline comments.Oct 26 2020, 2:08 PM
llvm/include/llvm/Support/TypeSize.h
56–67

@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.

125–128

Eek, good spot!

ctetreau added inline comments.Oct 26 2020, 4:17 PM
llvm/include/llvm/Support/TypeSize.h
56–67

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 updated this revision to Diff 301221.Oct 28 2020, 3:55 AM
sdesmalen retitled this revision from [NFCI] Add LinearPolyBase as base class for ElementCount, TypeSize and StackOffset. to [NFCI] Add StackOffset class and base classes for ElementCount, TypeSize..
sdesmalen edited the summary of this revision. (Show Details)
  • 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 marked 6 inline comments as done.Oct 28 2020, 4:01 AM

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
56–67

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 added inline comments.Oct 28 2020, 7:14 AM
llvm/include/llvm/Support/TypeSize.h
60

worth an assert that UniveriateDim is in range?

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

Looks good to me once you add that assert.

llvm/include/llvm/Support/TypeSize.h
56–67

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.

60

I think this would be a useful assert

sdesmalen marked 3 inline comments as done.

Added assert.

sdesmalen marked an inline comment as done.Oct 28 2020, 10:40 AM
sdesmalen added inline comments.
llvm/include/llvm/Support/TypeSize.h
60

Agreed, good catch!

david-arm accepted this revision.Oct 30 2020, 10:14 AM

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

This revision is now accepted and ready to land.Oct 30 2020, 10:14 AM
ctetreau accepted this revision.Oct 30 2020, 12:57 PM

Yeah, I think this is good to go

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