This is an archive of the discontinued LLVM Phabricator instance.

[SVE] Make ElementCount and TypeSize use a new PolySize class
ClosedPublic

Authored by david-arm on Sep 28 2020, 5:27 AM.

Details

Summary

I have introduced a new template PolySize class, where the template
parameter determines the type of quantity, i.e. for an element
count this is just an unsigned value. The ElementCount class is
now just a simple derivation of PolySize<unsigned>, whereas TypeSize
is more complicated because it still needs to contain the uint64_t
cast operator, since there are still many places in the code that
rely upon this implicit cast. As such the class also still needs
some of it's own operators.

I've tried to minimise the amount of code in the base PolySize
class, which led to a couple of changes:

  1. In some places we were relying on '==' operator comparisons

between ElementCounts and the scalar value 1. I didn't put this
operator in the new PolySize class, and thought it was actually
clearer to use the isScalar() function instead.

  1. I removed the isByteSized function and replaced it with calls

to isKnownMultipleOf(8).

I've also renamed NextPowerOf2 to be coefficientNextPowerOf2 so
that it's more consistent with coefficientDivideBy.

Diff Detail

Event Timeline

david-arm created this revision.Sep 28 2020, 5:27 AM
Herald added a reviewer: ftynse. · View Herald Transcript
Herald added projects: Restricted Project, Restricted Project. · View Herald Transcript
david-arm requested review of this revision.Sep 28 2020, 5:27 AM
ctetreau added inline comments.Sep 28 2020, 6:44 AM
llvm/include/llvm/Support/TypeSize.h
38

Why does there need to be a default constructor?

david-arm added inline comments.Sep 28 2020, 7:13 AM
llvm/include/llvm/Support/TypeSize.h
38

I think because there are places in the code base that rely upon it - this isn't something new as it was already in ElementCount. I think there is one example in llvm/include/llvm/IR/Intrinsics.h where the ElementCount is a member of a union. I'm pretty sure that removing the default constructor causes compilation errors, but I can try again to make sure.

ctetreau added inline comments.Sep 29 2020, 6:17 AM
llvm/include/llvm/Support/TypeSize.h
38

Assuming it's necessary to have this constructor, what should it do? Should it explicitly be defined to be {0, false}? Is it a garbage value?

I suppose {0, false} sort of is already a garbage value, so maybe everything can just assert that it's not this?

david-arm added inline comments.Sep 29 2020, 6:22 AM
llvm/include/llvm/Support/TypeSize.h
38

I think it's just like someone declaring a variable and then initialising it later, no different from a normal integer type that has a default constructor, i.e.

uint64_t SomeVal;
...
SomeVal = name == "Bob" ? 3 : 7;

If we want to remove the default constructor we could do it, but it will require some work to fix up cases where it's relied upon. I can certainly see what breaks when I remove it?

Hi @ctetreau so when I remove the default constructor I get this build error:

llvm/include/llvm/IR/Intrinsics.h: In static member function ‘static llvm::Intrinsic::IITDescriptor llvm::Intrinsic::IITDescriptor::getVector(unsigned int, bool)’:
llvm/include/llvm/IR/Intrinsics.h:191:21: error: use of deleted function ‘llvm::Intrinsic::IITDescriptor::IITDescriptor()’

191 |       IITDescriptor Result;
    |                     ^~~~~~

llvm/include/llvm/IR/Intrinsics.h:101:10: note: ‘llvm::Intrinsic::IITDescriptor::IITDescriptor()’ is implicitly deleted because the default definition would be ill-formed:

101 |   struct IITDescriptor {

llvm/include/llvm/IR/Intrinsics.h:101:10: error: no matching function for call to ‘llvm::PolySize<unsigned int>::PolySize()’

I think it's because we've included ElementCount within another struct. Ideally I'd like to avoid having to add asserts in PolySize member functions to ensure it's not a default value. I'll see if it's possible to change the IITDescriptor struct in some way so that this doesn't happen.

OK I can remove the default constructor by rewriting the IITDescriptor in such a way that it's no longer needed.

ctetreau added inline comments.Sep 29 2020, 7:56 AM
llvm/include/llvm/Support/TypeSize.h
38

I guess it might be nice to be able to do this. When ElementCount and TypeSize were just PODs, I was more OK with expecting the user to not mess it up, but since we're making them proper classes now...

I think if you make isScalable() and getKnownMinValue() assert that it's not {0, false}, then we can leave the default constructor for ergonomic purposes. If everything else were implemented in terms of these functions, then everything would be covered by the assert.

sdesmalen added inline comments.Sep 29 2020, 8:22 AM
llvm/include/llvm/Support/TypeSize.h
31

You've implemented PolySize more like the current TypeSize than an actual polynomial. That's fine I guess, but I'm currently looking at some interfaces that could use a general StackOffset. Since that currently lives in the AArch64 target, I might create a follow-up patch that generalises this further using a PolyBase class.

60

isScalar() only makes sense in the context of ElementCount and doesn't make sense in the context of TypeSize, so I believe this shouldn't live here.

david-arm added inline comments.Sep 29 2020, 8:51 AM
llvm/include/llvm/Support/TypeSize.h
31

Yeah, perhaps I remembered wrong, but I thought this was inline with what we'd discussed previously. This patch is mainly a refactoring effort to introduce the new class and is just the first step in the evolution. It seemed like refactoring + changing the fundamental nature in one patch might be too confusing that's all. For example, the isKnownXY functions will need rewriting to cope with full polynomials. We might even want to audit places where isScalable() is called to ensure the caller knows that returning true doesn't mean there are no fixed width elements. We might want to reverse the question to something like isFixed() perhaps?

60

Yes I think you're right. A polynomial definitely can be scalar, but that doesn't mean the scalar value is one.

ctetreau added inline comments.Sep 29 2020, 10:54 AM
llvm/include/llvm/Support/TypeSize.h
31

I think it makes sense to implement the actual abstract polynomial, and then have ElementCount and TypeSize inherit from them. So you could have something like:

template <typename NumT, typename VarT> class PolynomialTerm {
private:
  NumT Coefficient;
  VarT Var;
  // TODO: 2 or more vars in one term, assert that this doesn't happen for now
  // TODO: exponents
public:
  NumT getCoefficient() const;
  void setCoefficient(NumT N);
  VarT getVar() const;
  void setVar(VarT V);


  PolynomialTerm operator*(const PolynomialTerm& N) const;
  std::vector<PolynomialTerm> operator+(const PolynomialTerm& N) const;
  // any operator that makes sense for the abstract polynomial term

  bool isKnownLT(const PolynomialTerm& RHS) const;
  bool maybeLT(const PolynomialTerm& RHS) const;
  // all rest of the relations ...
};

And then your ElementCount looks like this:

class ElementCount : public PolynomialTerm<unsigned, bool> {
private:
  ElementCount(unsigned ElementQuantity, bool Scalable)
    : PolynomialTerm(ElementQuantity, Scalable) {}
public:
  bool isScalable() {
    return !getVar();
  }

  static ElementCount getFixed(unsigned N) {
    return ElementCount(N, false);
  }

  ElementCount divideCoefficientBy(unsigned N) {
    return ElementCount(getCoefficient() / N, getVar());
  }

  // etc... All the functions that make sense for ElementCount but not abstract polynomials
};

This will give us a reusable polynomial that can be extended in the future. If ElementCount and TypeSize are well-behaved, then they will just continue to work if the polynomial is extended in the future.

ctetreau added inline comments.Sep 30 2020, 6:27 AM
llvm/include/llvm/Support/TypeSize.h
31

the implementation of isScalable (should be return getVar();) in my example is wrong, but the point stands.

vkmr added inline comments.Sep 30 2020, 7:56 AM
llvm/include/llvm/Support/TypeSize.h
45

It might be useful to add an explicit getNone() (or getZero()) function that simply returns {0, false} value. For instance, there are places using Optional<ElementCount>for VF (and Optional<unsigned> where VF is not yet ported to ElementCount) and use None to represent VectorizationFailure. We already have isZero() and isNonZero() functions so a Zero getter should not be out of tune.

david-arm added inline comments.Sep 30 2020, 8:20 AM
llvm/include/llvm/Support/TypeSize.h
31

Hi @ctetreau I personally only intended this particular patch to be a refactoring effort where we can remove some duplication between the two classes and introduce some level of consistency. This first patch then leaves the door open for the introduction of a real polynomial later on. I know that not everyone is keen on using polynomials for ElementCount and TypeSize so I didn't want to make that decision without a strong consensus. The maths and the comparisons become a lot trickier for true polynomials too, not to mention the interfaces and class structures will need changing. I thought it best to only do that work when and where it was truly needed, and perhaps then we'll have a better understanding of the requirements. Is that ok?

sdesmalen added inline comments.Sep 30 2020, 8:53 AM
llvm/include/llvm/Support/TypeSize.h
31

I'd be okay with you keeping the scope of this patch as-is, I just wanted to let you know I'll probably work on a more generalised polynomial as a follow-up to implement a more generic class for StackOffset. The main concern we wanted to address was removing some duplication, which is what this patch achieves.
Do please add a TODO comment that explains there is future work required as this class doesn't yet implement a polynomial.

david-arm added inline comments.Sep 30 2020, 9:01 AM
llvm/include/llvm/Support/TypeSize.h
38

I tried replacing "PolySize() = default" with something explicit like "PolySize() : MinVal(0), IsScalable(false) {}", but sadly the compiler says this is not good enough for IITDescriptor. Since we can't be sure exactly what the default value is (I assume it's {0,false} but perhaps someone more knowledgeable can confirm?) I'd have to add asserts in isScalable, getKnownMinValue, getFixedSize and so on along the lines of:

assert(*this != PolySize())

david-arm updated this revision to Diff 295831.Oct 2 2020, 8:13 AM
david-arm edited the summary of this revision. (Show Details)
ctetreau added inline comments.Oct 5 2020, 9:25 AM
llvm/include/llvm/Support/TypeSize.h
31

@david-arm Sorry it took me so long to respond.

If this is is meant to be an temporary intermediate step with the goal of reducing code duplication, then I am fine with it. I agree with Sander that a TODO comment describing the current state and ultimate goal of the work should be added.

ctetreau added inline comments.Oct 5 2020, 9:37 AM
llvm/include/llvm/Support/TypeSize.h
38

I'm surprised that PolySize() : MinVal(0), IsScalable(false) {} doesn't work, what error does it give? Some issue with assigning 0 to the template field?

Regardless, I think you can assign values at the field headers, and it will be taken as the default. So do:

T MinVal = 0;            // The minimum value that it could be.
bool IsScalable = false; // If true, the total value is determined by multiplying
45

Bikeshedding: Maybe it should be named something like getNull() or getInvalid()? You propose using getZero() instead of having an Optional<ElementCount>. I think this usage is fine, but we should be clear that the thing is a garbage value, not zero in the mathematical sense. This lets us make the garbage value be something different in the future if there ends up being a better option.

vkmr added inline comments.Oct 5 2020, 5:34 PM
llvm/include/llvm/Support/TypeSize.h
45

Good point @ctetreau! I am not too keen on one name over other, but if I have to, my vote is for getNull(); I feel it best conveys the idea.

david-arm added inline comments.Oct 6 2020, 12:08 AM
llvm/include/llvm/Support/TypeSize.h
38

Hi @ctetreau, so having that constructor is fine, it's just that the compilation of IITDescriptor still fails with the same complaint about a lack of default constructors. :( Sometimes I feel C++ can be incredibly powerful, sometimes it just seems to thwart us at every corner! I'll try your suggestion of assigning default values.

45

Thanks for the suggestion @ctetreau, I'll change the name to getNull()!

david-arm updated this revision to Diff 296449.Oct 6 2020, 7:00 AM
david-arm marked an inline comment as done.Oct 6 2020, 7:02 AM

Hi @ctetreau, I decided to remove the default constructors as we only need a one or two line change llvm/include/llvm/IR/Intrinsics.h. This removes the need for asserts that we have a properly constructed object. Does this seem reasonable?

Hi @ctetreau, I decided to remove the default constructors as we only need a one or two line change llvm/include/llvm/IR/Intrinsics.h. This removes the need for asserts that we have a properly constructed object. Does this seem reasonable?

I think that would be idea.

ctetreau added inline comments.Oct 7 2020, 10:09 AM
llvm/include/llvm/Support/TypeSize.h
54

NIT: Implement in terms of isZero

156

NIT: prefer static_cast

177

Why provide this implicit conversion from base PolySize to ElementCount?

This could potentially lead to bugs, especially in the future when we introduce true a Polynomial type with exponents and/or multiple variables.

Is this neccesary to support cases like ElementCount EC = PolySize::getScalable(4)?

197

same as above, this implicit conversion could be dangerous

sdesmalen added inline comments.Oct 7 2020, 11:16 AM
llvm/include/llvm/Support/TypeSize.h
177

This is needed for the result from the base class' operators which will be of type PolySize<unsigned>. With this conversion, these can be freely converted to ElementCount and avoids having to re-specify all the operators. I've taken a similar approach in D88982 and wasn't entirely sure if this was actually unsafe.

The alternative is redefining the operators and calling the base-class, and making the conversion function private/protected to the deriving class.

I actually tried deriving from some other class, something like:

 template<typename Derived, typename Base>
class Operators {
  Derived operator+(const Derived &Other) { return (Derived) Base::operator+(Other); }
};

template<typename T> class Derived : public PolyBase<...>,
              public Operators<Derived, PolyBase> { ... };

but I got C++ template errors that I wasn't able to work around. Not sure if this should even be possible :)

david-arm updated this revision to Diff 297239.Oct 9 2020, 8:09 AM
  • Changed PolySize::isNonZero() to return !isZero()
  • Used static_cast in coefficientNextPowerOf2
david-arm marked 2 inline comments as done.Oct 9 2020, 8:09 AM
sdesmalen accepted this revision.Oct 9 2020, 10:02 AM

Thanks @david-arm, I think I'm happy enough with the changes you've made. Also some of these changes will be followed up further in D88982.
Please also give @ctetreau a chance to give his blessing before you commit.

This revision is now accepted and ready to land.Oct 9 2020, 10:02 AM
ctetreau accepted this revision.Oct 9 2020, 3:56 PM

looks good to me

I should be adding a fix for the build failure very soon. Will replace the initializer for IITDescriptor with {Vector, {0}}.