llvm dev - May 2020 - [Update][RFC] Refactor class hierarchy of VectorType in the IR

Hi,

                I just wanted to give an update on the progress of this work.
This morning I merged a patch to add the new vector types. I have added a
FixedVectorType, as proposed below. I also added a ScalableVectorType. I found
during my work that it is useful to be able to query
isa<ScalableVectorType>(Ty). Additionally, I was concerned that it would
become commonplace to take (isa<VectorType>(Ty) &&
!isa<FixedVectorType>(Ty)) to mean "is a scalable vector". This
is both more verbose, and not future proof if new vector types are ever added.

VectorType::get has been changed to construct a FixedVectorType if scalable =
false, or a ScalableVectorType if scalable = true. It is now impossible to
construct a base VectorType. Additionally, FixedVectorType::get and
ScalableVectorType::get functions have been added that allow you to directly
construct these types. I have also added an overload of VectorType::get that
takes a type, and a vector. This overload calls getElementCount() on the given
vector and uses that to construct a new VectorType. This is a convenience helper
for the cases where "I want a vector with the same shape as this other
vector, but a different element type." Calls to VectorType::get(SomeTy,
SomeVTy->getNumElements()) that try to implement this case are a very common
source of bugs when SomeVTy is scalable, use of this helper will eliminate these
bugs while also being more concise.

                Currently, VectorType still has its getNumElements() function,
and this function is still buggy in all the scenarios I describe below. Now that
the types exist in the codebase, I will begin to remove calls to getNumElements
through pointers to VectorType. My plan is to assume that all usages of
getNumElements() are correct and to unconditionally cast to FixedVectorType and
call it through the derived pointer. In places where this assumption is false,
the code will fail to cast, rather than silently miscompile. I will fix
breakages identified by existing test coverage. I also plan to make obvious
fixes where value is high or the amount of work to do so is low. There are too
many usage sites for one person to do this work alone. For a great many usage
sites, this assumption will be correct; all backend code for architectures that
don't have scalable vectors don't care about ScalableVectorType and many
target independent optimizations can't meaningfully do anything if they
don't know the actual number of vector lanes. Once the usages are fixed up,
I'll merge https://reviews.llvm.org/D78127 which will largely complete the
refactor.

                My request is that people please begin to use these types
correctly. If your code needs fixed width vectors, please use the
FixedVectorType directly, and somehow handle the case that a Type object is an
instance of ScalableVectorType. If your code is actually generic to both types
of vectors, please call getElementCount() instead of getNumElements(). And if
your code only cares about scalable vectors, you can directly use
ScalableVectorType. ScalableVectorType has a getMinNumElements() method that
gets the Min field from the element count. This is a very minor convenience, but
if you have a pointer to a ScalableVectorType, then you don't really care
about the value of getElementCount().Scalable.

Thanks,
                Christopher Tetreault

From: Chris Tetreault
Sent: Monday, March 9, 2020 12:06 PM
To: llvm-dev at lists.llvm.org
Subject: [RFC] Refactor class hierarchy of VectorType in the IR

Hi,
                I am helping with the effort to implement scalable vectors in
the codebase in order to add support for generating SVE code in the Arm backend.
I would like to propose a refactor of the Type class hierarchy in order to
eliminate issues related to the misuse of SequentialType::getNumElements(). I
would like to introduce a new class FixedVectorType that inherits from
SequentialType and VectorType. VectorType would no longer inherit from
SequentialType, instead directly inheriting from Type. After this change, it
will be statically impossible to accidentally call
SequentialType::getNumElements() via a VectorType pointer.
Background:
                Recently, scalable vectors have been introduced into the
codebase. Previously, vectors have been written <n x ty> in IR, where n is
a fixed number of elements known at compile time, and ty is some type. Scalable
vectors are written <vscale x n x ty> where vscale is a runtime constant
value. A new function has been added to VectorType (defined in
llvm/IR/DerivedTypes.h), getElementCount(), that returns an ElementCount, which
is defined as such in llvm/Support/TypeSize.h:
                class ElementCount {
public:
  unsigned Min;
  bool Scalable;
  ...
}
                Min is the minimum number of elements in the vector (the
"n" in <vscale x n x ty>), and Scalable is true if the vector is
scalable (true for <vscale x n x ty>, false for <n x ty>) The idea
is that if a vector is not scalable, then Min is exactly equal to the number of
vector elements, but if the vector is scalable, then the number of vector
elements is equal to some runtime-constant multiple of Min. The key takeaway
here is that scalable vectors and fixed length vectors need to be treated
differently by the compiler. For a fixed length vector, it is valid to iterate
over the vector elements, but this is impossible for a scalable vector.
Discussion:
The trouble is that all instances of VectorType have getNumElements() inherited
from SequentialType. Prior to the introduction of scalable vectors, this
function was guaranteed to return the number of elements in a vector or array.
Today, there is a comment that documents the fact that this returns only the
minimum number of elements for scalable vectors, however there exists a ton of
code in the codebase that is now misusing getNumElements(). Some examples:
                Auto *V = VectorType::get(Ty,
SomeOtherVec->getNumElements());
                This code was previously perfectly fine but is incorrect for
scalable vectors. When scalable vectors were introduced VectorType::get() was
refactored to take a bool to tell if the vector is scalable. This bool has a
default value of false. In this example, get() is returning a non-scalable
vector even if SomeOtherVec was scalable. This will manifest later in some
unrelated code as a type mismatch between a scalable and fixed length vector.
                for (unsigned I = 0; I < SomeVec->getNumElements(); ++I) {
... }
                Previously, since there was no notion of scalable vectors, this
was perfectly reasonable code. However, for scalable vectors, this is always a
bug.
                With vigilance in code review, and good test coverage we will
eventually find and squash most of these bugs. Unfortunately, code review is
hard, and test coverage isn't perfect. Bugs will continue to slip through as
long as it's easier to do the wrong thing.
                One other factor to consider, is that there is a great deal of
code which deals exclusively with fixed length vectors. Any backend for which
there are no scalable vectors should not need to care about their existence.
Even in Arm, if Neon code is being generated, then the vectors will never be
scalable. In this code, the current status quo is perfectly fine, and any code
related to checking if the vector is scalable is just noise.
Proposal:
                In order to support users who only need fixed width vectors, and
to ensure that nobody can accidentally call getNumElements() on a scalable
vector, I am proposing the introduction of a new FixedVectorType which inherits
from both VectorType and SequentialType. In turn, VectorType will no longer
inherit from SequentialType. An example of what this will look like, with some
misc. functions omitted for clarity:
class VectorType : public Type {
public:
  static VectorType *get(Type *ElementType, ElementCount EC);

  Type *getElementType() const;
  ElementCount getElementCount() const;
  bool isScalable() const;
};

class FixedVectorType : public VectorType, public SequentialType {
public:
  static FixedVectorType *get(Type *ElementType, unsigned NumElts);
};

class SequentialType : public CompositeType {
public:
  uint64_t getNumElements() const { return NumElements; }
};
                In this proposed architecture, VectorType does not have a
getNumElements() function because it does not inherit from SequentialType. In
generic code, users will call VectorType::get() to obtain a new instance of
VectorType just as they always have. VectorType implements the safe subset of
functionality of fixed and scalable vectors that is suitable for use anywhere.
If the user passes false to the scalable parameter of get(), they will get an
instance of FixedVectorType back. Users can then inspect its type and cast it to
FixedVectorType using the usual mechanisms. In code that deals exclusively in
fixed length vectors, the user can call FixedVectorType::get() to directly get
an instance of FixedVectorType, and their code can remain largely unchanged from
how it was prior to the introduction of scalable vectors. At this time, there
exists no use case that is only valid for scalable vectors, so no
ScalableVectorType is being added.
                With this change, in generic code it is now impossible to
accidentally call getNumElements() on a scalable vector. If a user tries to pass
a scalable vector to a function that expects a fixed length vector, they will
encounter a compilation failure at the site of the bug, rather than a runtime
error in some unrelated code. If a user attempts to cast a scalable vector to
FixedVectorType, the cast will fail at the call site. This will make it easier
to track down all the places that are currently incorrect, and will prevent
future developers from introducing bugs by misusing getNumElements().
Outstanding design choice:
                One issue with this architecture as proposed is the fact that
SequentialType (by way of CompositeType) inherits from Type. This introduces a
diamond inheritance in FixedVectorType. Unfortunately, llvm::cast uses a c-style
cast internally, so we cannot use virtual inheritance to resolve this issue.
Thus, we have a few options:

  1.  Break CompositeType's inheritance on Type and introduce functions to
convert from a Type to a CompositeType and vice versa. The conversion from
CompositeType is always safe because all instances of CompositeType (StructType,
ArrayType, and FixedVectorType) are instances of Type. A CompositeType can be
cast to the most derived class, then back to Type. The other way is not always
safe, so a function will need to be added to check if a Type is an instance of
CompositeType. This change is not that big, and I have a prototype
implementation up at https://reviews.llvm.org/D75486 ([SVE] Make CompositeType
not inherit from Type)
     *   Pros: this approach would result in minimal changes to the codebase. If
the llvm casts can be made to work for the conversion functions, then it would
touch very few files.
     *   Cons: There are those who think that CompositeType adds little value
and should be removed. Now would be an ideal time to do this. Additionally, the
conversion functions would be more complicated if we left CompositeType in.
  2.  Remove CompositeType and break SequentialType's inheritance of Type.
Add functions to convert a SequentialType to and from Type. The conversion
functions would work the same as those in option 1 above. Currently, there
exists only one class that derives directly from CompositeType: StructType. The
functionality of CompositeType can be directly moved into StructType, and APIs
that use CompositeType can directly use Type and cast appropriately. We feel
that this would be a fairly simple change, and we have a prototype
implementation up at https://reviews.llvm.org/D75660 (Remove CompositeType
class)
     *   Pros: Removing CompositeType would simplify the type hierarchy. Leaving
SequentialType in would simplify some code and be more typesafe than having a
getSequentialNumElements on Type.
     *   Cons: The value of SequentialType has also been called into question.
If we wanted to remove it, now would be a good time. Conversion functions add
complexity to the design. Introduces additional casting from Type.
  3.  Remove CompositeType and SequentialType. Roll the functions directly into
the most derived classes. A helper function can be added to Type to handle
choosing from FixedVectorType and ArrayType and calling getNumElements():
static unsigned getSequentialNumElements() {
  assert(isSequentialType()); // This already exists and does the
                              // right thing
  if (auto *AT = dyn_cast<ArrayType>(this))
    return AT->getNumElements();
  return cast<FixedVectorType>(this)->getNumElements();
}
A prototype implementation of this strategy can be found at
https://reviews.llvm.org/D75661 (Remove SequentialType from the type heirarchy.)

     *   Pros: By removing the multiple inheritance completely, we greatly
simplify the design and eliminate the need for any conversion functions. The
value of CompositeType and SequentialType has been called into question, and
removing them now might be of benefit to the codebase
     *   Cons: getSequentialNumElements() has similar issues to those that we
are trying to solve in the first place and potentially subverts the whole
design. Omitting getSequentialNumElements() would add lots of code duplication.
Introduces additional casting from Type.
I believe that all three of these options are reasonable. My personal preference
is currently option 2. I think that option 3's getSequentialNumElements()
subverts the design because every Type has getSequentialNumElements(), it is
tempting to just call it. However, the cast will fail at the call site in debug,
and in release it will return a garbage value rather than a value that works
most of the time. For option 1, the existence of CompositeType complicates the
conversion logic for little benefit.
Conclusion:
                Thank you for your time in reviewing this RFC. Your feedback on
my work is greatly appreciated.

Thank you,
                Christopher Tetreault

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200422/f3c37a12/attachment-0001.html>

Hi Chris,

this is a bit late, but I want to thank you for the work you're doing
and the careful approach you're taking, e.g. with the warning in
VectorType::getNumElements(). Once you're closer to being able to
remove the method entirely, I'd ask you to please mark it as
deprecated first. This would be a great help for those of us who track
master closely and do a lot of work upstream, but also have a frontend
that is out-of-tree -- we obviously wouldn't ask you to do the work of
removing uses of getNumElements() in our frontend, but going the
deprecation route is hopefully not a big burden and smooths the
upgrade process significantly.

Cheers,
Nicolai

On Wed, Apr 22, 2020 at 8:19 PM Chris Tetreault via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi,
>
>
>
>                 I just wanted to give an update on the progress of this
work. This morning I merged a patch to add the new vector types. I have added a
FixedVectorType, as proposed below. I also added a ScalableVectorType. I found
during my work that it is useful to be able to query
isa<ScalableVectorType>(Ty). Additionally, I was concerned that it would
become commonplace to take (isa<VectorType>(Ty) &&
!isa<FixedVectorType>(Ty)) to mean “is a scalable vector”. This is both
more verbose, and not future proof if new vector types are ever added.
>
>
>
> VectorType::get has been changed to construct a FixedVectorType if scalable
= false, or a ScalableVectorType if scalable = true. It is now impossible to
construct a base VectorType. Additionally, FixedVectorType::get and
ScalableVectorType::get functions have been added that allow you to directly
construct these types. I have also added an overload of VectorType::get that
takes a type, and a vector. This overload calls getElementCount() on the given
vector and uses that to construct a new VectorType. This is a convenience helper
for the cases where “I want a vector with the same shape as this other vector,
but a different element type.” Calls to VectorType::get(SomeTy,
SomeVTy->getNumElements()) that try to implement this case are a very common
source of bugs when SomeVTy is scalable, use of this helper will eliminate these
bugs while also being more concise.
>
>
>
>                 Currently, VectorType still has its getNumElements()
function, and this function is still buggy in all the scenarios I describe
below. Now that the types exist in the codebase, I will begin to remove calls to
getNumElements through pointers to VectorType. My plan is to assume that all
usages of getNumElements() are correct and to unconditionally cast to
FixedVectorType and call it through the derived pointer. In places where this
assumption is false, the code will fail to cast, rather than silently
miscompile. I will fix breakages identified by existing test coverage. I also
plan to make obvious fixes where value is high or the amount of work to do so is
low. There are too many usage sites for one person to do this work alone. For a
great many usage sites, this assumption will be correct; all backend code for
architectures that don’t have scalable vectors don’t care about
ScalableVectorType and many target independent optimizations can’t meaningfully
do anything if they don’t know the actual number of vector lanes. Once the
usages are fixed up, I’ll merge https://reviews.llvm.org/D78127 which will
largely complete the refactor.
>
>
>
>                 My request is that people please begin to use these types
correctly. If your code needs fixed width vectors, please use the
FixedVectorType directly, and somehow handle the case that a Type object is an
instance of ScalableVectorType. If your code is actually generic to both types
of vectors, please call getElementCount() instead of getNumElements(). And if
your code only cares about scalable vectors, you can directly use
ScalableVectorType. ScalableVectorType has a getMinNumElements() method that
gets the Min field from the element count. This is a very minor convenience, but
if you have a pointer to a ScalableVectorType, then you don’t really care about
the value of getElementCount().Scalable.
>
>
>
> Thanks,
>
>                 Christopher Tetreault
>
>
>
> From: Chris Tetreault
> Sent: Monday, March 9, 2020 12:06 PM
> To: llvm-dev at lists.llvm.org
> Subject: [RFC] Refactor class hierarchy of VectorType in the IR
>
>
>
> Hi,
>
>                 I am helping with the effort to implement scalable vectors
in the codebase in order to add support for generating SVE code in the Arm
backend. I would like to propose a refactor of the Type class hierarchy in order
to eliminate issues related to the misuse of SequentialType::getNumElements(). I
would like to introduce a new class FixedVectorType that inherits from
SequentialType and VectorType. VectorType would no longer inherit from
SequentialType, instead directly inheriting from Type. After this change, it
will be statically impossible to accidentally call
SequentialType::getNumElements() via a VectorType pointer.
>
> Background:
>
>                 Recently, scalable vectors have been introduced into the
codebase. Previously, vectors have been written <n x ty> in IR, where n is
a fixed number of elements known at compile time, and ty is some type. Scalable
vectors are written <vscale x n x ty> where vscale is a runtime constant
value. A new function has been added to VectorType (defined in
llvm/IR/DerivedTypes.h), getElementCount(), that returns an ElementCount, which
is defined as such in llvm/Support/TypeSize.h:
>
>                 class ElementCount {
>
> public:
>
>   unsigned Min;
>
>   bool Scalable;
>
>   …
>
> }
>
>                 Min is the minimum number of elements in the vector (the
“n” in <vscale x n x ty>), and Scalable is true if the vector is scalable
(true for <vscale x n x ty>, false for <n x ty>) The idea is that if
a vector is not scalable, then Min is exactly equal to the number of vector
elements, but if the vector is scalable, then the number of vector elements is
equal to some runtime-constant multiple of Min. The key takeaway here is that
scalable vectors and fixed length vectors need to be treated differently by the
compiler. For a fixed length vector, it is valid to iterate over the vector
elements, but this is impossible for a scalable vector.
>
> Discussion:
>
> The trouble is that all instances of VectorType have getNumElements()
inherited from SequentialType. Prior to the introduction of scalable vectors,
this function was guaranteed to return the number of elements in a vector or
array. Today, there is a comment that documents the fact that this returns only
the minimum number of elements for scalable vectors, however there exists a ton
of code in the codebase that is now misusing getNumElements(). Some examples:
>
>                 Auto *V = VectorType::get(Ty,
SomeOtherVec->getNumElements());
>
>                 This code was previously perfectly fine but is incorrect
for scalable vectors. When scalable vectors were introduced VectorType::get()
was refactored to take a bool to tell if the vector is scalable. This bool has a
default value of false. In this example, get() is returning a non-scalable
vector even if SomeOtherVec was scalable. This will manifest later in some
unrelated code as a type mismatch between a scalable and fixed length vector.
>
>                 for (unsigned I = 0; I < SomeVec->getNumElements();
++I) { … }
>
>                 Previously, since there was no notion of scalable vectors,
this was perfectly reasonable code. However, for scalable vectors, this is
always a bug.
>
>                 With vigilance in code review, and good test coverage we
will eventually find and squash most of these bugs. Unfortunately, code review
is hard, and test coverage isn’t perfect. Bugs will continue to slip through as
long as it’s easier to do the wrong thing.
>
>                 One other factor to consider, is that there is a great deal
of code which deals exclusively with fixed length vectors. Any backend for which
there are no scalable vectors should not need to care about their existence.
Even in Arm, if Neon code is being generated, then the vectors will never be
scalable. In this code, the current status quo is perfectly fine, and any code
related to checking if the vector is scalable is just noise.
>
> Proposal:
>
>                 In order to support users who only need fixed width
vectors, and to ensure that nobody can accidentally call getNumElements() on a
scalable vector, I am proposing the introduction of a new FixedVectorType which
inherits from both VectorType and SequentialType. In turn, VectorType will no
longer inherit from SequentialType. An example of what this will look like, with
some misc. functions omitted for clarity:
>
> class VectorType : public Type {
>
> public:
>
>   static VectorType *get(Type *ElementType, ElementCount EC);
>
>
>
>   Type *getElementType() const;
>
>   ElementCount getElementCount() const;
>
>   bool isScalable() const;
>
> };
>
>
>
> class FixedVectorType : public VectorType, public SequentialType {
>
> public:
>
>   static FixedVectorType *get(Type *ElementType, unsigned NumElts);
>
> };
>
>
>
> class SequentialType : public CompositeType {
>
> public:
>
>   uint64_t getNumElements() const { return NumElements; }
>
> };
>
>                 In this proposed architecture, VectorType does not have a
getNumElements() function because it does not inherit from SequentialType. In
generic code, users will call VectorType::get() to obtain a new instance of
VectorType just as they always have. VectorType implements the safe subset of
functionality of fixed and scalable vectors that is suitable for use anywhere.
If the user passes false to the scalable parameter of get(), they will get an
instance of FixedVectorType back. Users can then inspect its type and cast it to
FixedVectorType using the usual mechanisms. In code that deals exclusively in
fixed length vectors, the user can call FixedVectorType::get() to directly get
an instance of FixedVectorType, and their code can remain largely unchanged from
how it was prior to the introduction of scalable vectors. At this time, there
exists no use case that is only valid for scalable vectors, so no
ScalableVectorType is being added.
>
>                 With this change, in generic code it is now impossible to
accidentally call getNumElements() on a scalable vector. If a user tries to pass
a scalable vector to a function that expects a fixed length vector, they will
encounter a compilation failure at the site of the bug, rather than a runtime
error in some unrelated code. If a user attempts to cast a scalable vector to
FixedVectorType, the cast will fail at the call site. This will make it easier
to track down all the places that are currently incorrect, and will prevent
future developers from introducing bugs by misusing getNumElements().
>
> Outstanding design choice:
>
>                 One issue with this architecture as proposed is the fact
that SequentialType (by way of CompositeType) inherits from Type. This
introduces a diamond inheritance in FixedVectorType. Unfortunately, llvm::cast
uses a c-style cast internally, so we cannot use virtual inheritance to resolve
this issue. Thus, we have a few options:
>
> Break CompositeType’s inheritance on Type and introduce functions to
convert from a Type to a CompositeType and vice versa. The conversion from
CompositeType is always safe because all instances of CompositeType (StructType,
ArrayType, and FixedVectorType) are instances of Type. A CompositeType can be
cast to the most derived class, then back to Type. The other way is not always
safe, so a function will need to be added to check if a Type is an instance of
CompositeType. This change is not that big, and I have a prototype
implementation up at https://reviews.llvm.org/D75486 ([SVE] Make CompositeType
not inherit from Type)
>
> Pros: this approach would result in minimal changes to the codebase. If the
llvm casts can be made to work for the conversion functions, then it would touch
very few files.
> Cons: There are those who think that CompositeType adds little value and
should be removed. Now would be an ideal time to do this. Additionally, the
conversion functions would be more complicated if we left CompositeType in.
>
> Remove CompositeType and break SequentialType’s inheritance of Type. Add
functions to convert a SequentialType to and from Type. The conversion functions
would work the same as those in option 1 above. Currently, there exists only one
class that derives directly from CompositeType: StructType. The functionality of
CompositeType can be directly moved into StructType, and APIs that use
CompositeType can directly use Type and cast appropriately. We feel that this
would be a fairly simple change, and we have a prototype implementation up at
https://reviews.llvm.org/D75660 (Remove CompositeType class)
>
> Pros: Removing CompositeType would simplify the type hierarchy. Leaving
SequentialType in would simplify some code and be more typesafe than having a
getSequentialNumElements on Type.
> Cons: The value of SequentialType has also been called into question. If we
wanted to remove it, now would be a good time. Conversion functions add
complexity to the design. Introduces additional casting from Type.
>
> Remove CompositeType and SequentialType. Roll the functions directly into
the most derived classes. A helper function can be added to Type to handle
choosing from FixedVectorType and ArrayType and calling getNumElements():
>
> static unsigned getSequentialNumElements() {
>
>   assert(isSequentialType()); // This already exists and does the
>
>                               // right thing
>
>   if (auto *AT = dyn_cast<ArrayType>(this))
>
>     return AT->getNumElements();
>
>   return cast<FixedVectorType>(this)->getNumElements();
>
> }
>
> A prototype implementation of this strategy can be found at
https://reviews.llvm.org/D75661 (Remove SequentialType from the type heirarchy.)
>
> Pros: By removing the multiple inheritance completely, we greatly simplify
the design and eliminate the need for any conversion functions. The value of
CompositeType and SequentialType has been called into question, and removing
them now might be of benefit to the codebase
> Cons: getSequentialNumElements() has similar issues to those that we are
trying to solve in the first place and potentially subverts the whole design.
Omitting getSequentialNumElements() would add lots of code duplication.
Introduces additional casting from Type.
>
> I believe that all three of these options are reasonable. My personal
preference is currently option 2. I think that option 3’s
getSequentialNumElements() subverts the design because every Type has
getSequentialNumElements(), it is tempting to just call it. However, the cast
will fail at the call site in debug, and in release it will return a garbage
value rather than a value that works most of the time. For option 1, the
existence of CompositeType complicates the conversion logic for little benefit.
>
> Conclusion:
>
>                 Thank you for your time in reviewing this RFC. Your
feedback on my work is greatly appreciated.
>
>
>
> Thank you,
>
>                 Christopher Tetreault
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


-- 
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.

Nicolai,

   My plan is to remove getNumElements() as soon as possible. Hopefully within
the next few weeks. I just made a patch on my machine that marks it deprecated,
and it generates a ton of warnings. Given that some build bots build with
-Werror, I don't think we can mark it deprecated unless all the usages are
first removed.

   It occurs to me now that it might be good to mark it deprecated for some
period of time to be nice to downstreams. I maintain a downstream that attempts
to stay up to date with master myself, and it would probably make my life easier
if getNumElements didn't just suddenly go away. I think the -Werror build
bots would prevent most people from re-introducing it, we would just have to be
very vigilant to ensure that nobody un-deprecates it.

   Since most usages of getNumElements() are either easy to fix (by casting to
FixedVectorType), or likely are causing miscompilation, I would prefer to keep
the amount of time it remains as short as possible. What do you think would be a
reasonable period of time for it to be deprecated? 2 weeks?

   I would also like to add that assuming you have integrated
https://reviews.llvm.org/rG2dea3f129878e929e5d1f00b91a622eb1ec8be4e, you should
probably start fixing up usages of getNumElements() now.

thanks,
   Christopher Tetreault

-----Original Message-----
From: Nicolai Hähnle <nhaehnle at gmail.com>
Sent: Tuesday, May 5, 2020 4:23 AM
To: Chris Tetreault <ctetreau at quicinc.com>
Cc: LLVM Dev <llvm-dev at lists.llvm.org>
Subject: [EXT] Re: [llvm-dev] [Update][RFC] Refactor class hierarchy of
VectorType in the IR

Hi Chris,

this is a bit late, but I want to thank you for the work you're doing and
the careful approach you're taking, e.g. with the warning in
VectorType::getNumElements(). Once you're closer to being able to remove the
method entirely, I'd ask you to please mark it as deprecated first. This
would be a great help for those of us who track master closely and do a lot of
work upstream, but also have a frontend that is out-of-tree -- we obviously
wouldn't ask you to do the work of removing uses of getNumElements() in our
frontend, but going the deprecation route is hopefully not a big burden and
smooths the upgrade process significantly.

Cheers,
Nicolai

On Wed, Apr 22, 2020 at 8:19 PM Chris Tetreault via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>
> Hi,
>
>
>
>                 I just wanted to give an update on the progress of this
work. This morning I merged a patch to add the new vector types. I have added a
FixedVectorType, as proposed below. I also added a ScalableVectorType. I found
during my work that it is useful to be able to query
isa<ScalableVectorType>(Ty). Additionally, I was concerned that it would
become commonplace to take (isa<VectorType>(Ty) &&
!isa<FixedVectorType>(Ty)) to mean “is a scalable vector”. This is both
more verbose, and not future proof if new vector types are ever added.
>
>
>
> VectorType::get has been changed to construct a FixedVectorType if scalable
= false, or a ScalableVectorType if scalable = true. It is now impossible to
construct a base VectorType. Additionally, FixedVectorType::get and
ScalableVectorType::get functions have been added that allow you to directly
construct these types. I have also added an overload of VectorType::get that
takes a type, and a vector. This overload calls getElementCount() on the given
vector and uses that to construct a new VectorType. This is a convenience helper
for the cases where “I want a vector with the same shape as this other vector,
but a different element type.” Calls to VectorType::get(SomeTy,
SomeVTy->getNumElements()) that try to implement this case are a very common
source of bugs when SomeVTy is scalable, use of this helper will eliminate these
bugs while also being more concise.
>
>
>
>                 Currently, VectorType still has its getNumElements()
function, and this function is still buggy in all the scenarios I describe
below. Now that the types exist in the codebase, I will begin to remove calls to
getNumElements through pointers to VectorType. My plan is to assume that all
usages of getNumElements() are correct and to unconditionally cast to
FixedVectorType and call it through the derived pointer. In places where this
assumption is false, the code will fail to cast, rather than silently
miscompile. I will fix breakages identified by existing test coverage. I also
plan to make obvious fixes where value is high or the amount of work to do so is
low. There are too many usage sites for one person to do this work alone. For a
great many usage sites, this assumption will be correct; all backend code for
architectures that don’t have scalable vectors don’t care about
ScalableVectorType and many target independent optimizations can’t meaningfully
do anything if they don’t know the actual number of vector lanes. Once the
usages are fixed up, I’ll merge https://reviews.llvm.org/D78127 which will
largely complete the refactor.
>
>
>
>                 My request is that people please begin to use these types
correctly. If your code needs fixed width vectors, please use the
FixedVectorType directly, and somehow handle the case that a Type object is an
instance of ScalableVectorType. If your code is actually generic to both types
of vectors, please call getElementCount() instead of getNumElements(). And if
your code only cares about scalable vectors, you can directly use
ScalableVectorType. ScalableVectorType has a getMinNumElements() method that
gets the Min field from the element count. This is a very minor convenience, but
if you have a pointer to a ScalableVectorType, then you don’t really care about
the value of getElementCount().Scalable.
>
>
>
> Thanks,
>
>                 Christopher Tetreault
>
>
>
> From: Chris Tetreault
> Sent: Monday, March 9, 2020 12:06 PM
> To: llvm-dev at lists.llvm.org
> Subject: [RFC] Refactor class hierarchy of VectorType in the IR
>
>
>
> Hi,
>
>                 I am helping with the effort to implement scalable vectors
in the codebase in order to add support for generating SVE code in the Arm
backend. I would like to propose a refactor of the Type class hierarchy in order
to eliminate issues related to the misuse of SequentialType::getNumElements(). I
would like to introduce a new class FixedVectorType that inherits from
SequentialType and VectorType. VectorType would no longer inherit from
SequentialType, instead directly inheriting from Type. After this change, it
will be statically impossible to accidentally call
SequentialType::getNumElements() via a VectorType pointer.
>
> Background:
>
>                 Recently, scalable vectors have been introduced into the
codebase. Previously, vectors have been written <n x ty> in IR, where n is
a fixed number of elements known at compile time, and ty is some type. Scalable
vectors are written <vscale x n x ty> where vscale is a runtime constant
value. A new function has been added to VectorType (defined in
llvm/IR/DerivedTypes.h), getElementCount(), that returns an ElementCount, which
is defined as such in llvm/Support/TypeSize.h:
>
>                 class ElementCount {
>
> public:
>
>   unsigned Min;
>
>   bool Scalable;
>
>   …
>
> }
>
>                 Min is the minimum number of elements in the vector (the
“n” in <vscale x n x ty>), and Scalable is true if the vector is scalable
(true for <vscale x n x ty>, false for <n x ty>) The idea is that if
a vector is not scalable, then Min is exactly equal to the number of vector
elements, but if the vector is scalable, then the number of vector elements is
equal to some runtime-constant multiple of Min. The key takeaway here is that
scalable vectors and fixed length vectors need to be treated differently by the
compiler. For a fixed length vector, it is valid to iterate over the vector
elements, but this is impossible for a scalable vector.
>
> Discussion:
>
> The trouble is that all instances of VectorType have getNumElements()
inherited from SequentialType. Prior to the introduction of scalable vectors,
this function was guaranteed to return the number of elements in a vector or
array. Today, there is a comment that documents the fact that this returns only
the minimum number of elements for scalable vectors, however there exists a ton
of code in the codebase that is now misusing getNumElements(). Some examples:
>
>                 Auto *V = VectorType::get(Ty,
> SomeOtherVec->getNumElements());
>
>                 This code was previously perfectly fine but is incorrect
for scalable vectors. When scalable vectors were introduced VectorType::get()
was refactored to take a bool to tell if the vector is scalable. This bool has a
default value of false. In this example, get() is returning a non-scalable
vector even if SomeOtherVec was scalable. This will manifest later in some
unrelated code as a type mismatch between a scalable and fixed length vector.
>
>                 for (unsigned I = 0; I < SomeVec->getNumElements();
> ++I) { … }
>
>                 Previously, since there was no notion of scalable vectors,
this was perfectly reasonable code. However, for scalable vectors, this is
always a bug.
>
>                 With vigilance in code review, and good test coverage we
will eventually find and squash most of these bugs. Unfortunately, code review
is hard, and test coverage isn’t perfect. Bugs will continue to slip through as
long as it’s easier to do the wrong thing.
>
>                 One other factor to consider, is that there is a great deal
of code which deals exclusively with fixed length vectors. Any backend for which
there are no scalable vectors should not need to care about their existence.
Even in Arm, if Neon code is being generated, then the vectors will never be
scalable. In this code, the current status quo is perfectly fine, and any code
related to checking if the vector is scalable is just noise.
>
> Proposal:
>
>                 In order to support users who only need fixed width
vectors, and to ensure that nobody can accidentally call getNumElements() on a
scalable vector, I am proposing the introduction of a new FixedVectorType which
inherits from both VectorType and SequentialType. In turn, VectorType will no
longer inherit from SequentialType. An example of what this will look like, with
some misc. functions omitted for clarity:
>
> class VectorType : public Type {
>
> public:
>
>   static VectorType *get(Type *ElementType, ElementCount EC);
>
>
>
>   Type *getElementType() const;
>
>   ElementCount getElementCount() const;
>
>   bool isScalable() const;
>
> };
>
>
>
> class FixedVectorType : public VectorType, public SequentialType {
>
> public:
>
>   static FixedVectorType *get(Type *ElementType, unsigned NumElts);
>
> };
>
>
>
> class SequentialType : public CompositeType {
>
> public:
>
>   uint64_t getNumElements() const { return NumElements; }
>
> };
>
>                 In this proposed architecture, VectorType does not have a
getNumElements() function because it does not inherit from SequentialType. In
generic code, users will call VectorType::get() to obtain a new instance of
VectorType just as they always have. VectorType implements the safe subset of
functionality of fixed and scalable vectors that is suitable for use anywhere.
If the user passes false to the scalable parameter of get(), they will get an
instance of FixedVectorType back. Users can then inspect its type and cast it to
FixedVectorType using the usual mechanisms. In code that deals exclusively in
fixed length vectors, the user can call FixedVectorType::get() to directly get
an instance of FixedVectorType, and their code can remain largely unchanged from
how it was prior to the introduction of scalable vectors. At this time, there
exists no use case that is only valid for scalable vectors, so no
ScalableVectorType is being added.
>
>                 With this change, in generic code it is now impossible to
accidentally call getNumElements() on a scalable vector. If a user tries to pass
a scalable vector to a function that expects a fixed length vector, they will
encounter a compilation failure at the site of the bug, rather than a runtime
error in some unrelated code. If a user attempts to cast a scalable vector to
FixedVectorType, the cast will fail at the call site. This will make it easier
to track down all the places that are currently incorrect, and will prevent
future developers from introducing bugs by misusing getNumElements().
>
> Outstanding design choice:
>
>                 One issue with this architecture as proposed is the fact
that SequentialType (by way of CompositeType) inherits from Type. This
introduces a diamond inheritance in FixedVectorType. Unfortunately, llvm::cast
uses a c-style cast internally, so we cannot use virtual inheritance to resolve
this issue. Thus, we have a few options:
>
> Break CompositeType’s inheritance on Type and introduce functions to
> convert from a Type to a CompositeType and vice versa. The conversion
> from CompositeType is always safe because all instances of
> CompositeType (StructType, ArrayType, and FixedVectorType) are
> instances of Type. A CompositeType can be cast to the most derived
> class, then back to Type. The other way is not always safe, so a
> function will need to be added to check if a Type is an instance of
> CompositeType. This change is not that big, and I have a prototype
> implementation up at https://reviews.llvm.org/D75486 ([SVE] Make
> CompositeType not inherit from Type)
>
> Pros: this approach would result in minimal changes to the codebase. If the
llvm casts can be made to work for the conversion functions, then it would touch
very few files.
> Cons: There are those who think that CompositeType adds little value and
should be removed. Now would be an ideal time to do this. Additionally, the
conversion functions would be more complicated if we left CompositeType in.
>
> Remove CompositeType and break SequentialType’s inheritance of Type.
> Add functions to convert a SequentialType to and from Type. The
> conversion functions would work the same as those in option 1 above.
> Currently, there exists only one class that derives directly from
> CompositeType: StructType. The functionality of CompositeType can be
> directly moved into StructType, and APIs that use CompositeType can
> directly use Type and cast appropriately. We feel that this would be a
> fairly simple change, and we have a prototype implementation up at
> https://reviews.llvm.org/D75660 (Remove CompositeType class)
>
> Pros: Removing CompositeType would simplify the type hierarchy. Leaving
SequentialType in would simplify some code and be more typesafe than having a
getSequentialNumElements on Type.
> Cons: The value of SequentialType has also been called into question. If we
wanted to remove it, now would be a good time. Conversion functions add
complexity to the design. Introduces additional casting from Type.
>
> Remove CompositeType and SequentialType. Roll the functions directly into
the most derived classes. A helper function can be added to Type to handle
choosing from FixedVectorType and ArrayType and calling getNumElements():
>
> static unsigned getSequentialNumElements() {
>
>   assert(isSequentialType()); // This already exists and does the
>
>                               // right thing
>
>   if (auto *AT = dyn_cast<ArrayType>(this))
>
>     return AT->getNumElements();
>
>   return cast<FixedVectorType>(this)->getNumElements();
>
> }
>
> A prototype implementation of this strategy can be found at
> https://reviews.llvm.org/D75661 (Remove SequentialType from the type
> heirarchy.)
>
> Pros: By removing the multiple inheritance completely, we greatly
> simplify the design and eliminate the need for any conversion
> functions. The value of CompositeType and SequentialType has been
> called into question, and removing them now might be of benefit to the
> codebase
> Cons: getSequentialNumElements() has similar issues to those that we are
trying to solve in the first place and potentially subverts the whole design.
Omitting getSequentialNumElements() would add lots of code duplication.
Introduces additional casting from Type.
>
> I believe that all three of these options are reasonable. My personal
preference is currently option 2. I think that option 3’s
getSequentialNumElements() subverts the design because every Type has
getSequentialNumElements(), it is tempting to just call it. However, the cast
will fail at the call site in debug, and in release it will return a garbage
value rather than a value that works most of the time. For option 1, the
existence of CompositeType complicates the conversion logic for little benefit.
>
> Conclusion:
>
>                 Thank you for your time in reviewing this RFC. Your
feedback on my work is greatly appreciated.
>
>
>
> Thank you,
>
>                 Christopher Tetreault
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
Lerne, wie die Welt wirklich ist,
aber vergiss niemals, wie sie sein sollte.