More extendable LaneBitmask

[kparzysz]

Summary

This is in response to recent emails about extending the numbers of available lanes. While that problem went away, this is a more generic approach than what we have at the moment.
I haven't tested it beyond "check-llvm". I'm wondering what you think.

[kparzysz]

lib/CodeGen/MIRParser/MIParser.cpp

548

This part is not complete.

[MatzeB]

• I would be slightly hesitant here, as it complicates code and none of the public targets needs this. We don't even try the "uint64_t" instead of "unsigned" step but instead just make it all complicated right away...
• I would not commit this without careful measurements to ensure that compilers indeed optimize all of this away and we don't have a compiletime impact.
• You probably can use some of the APInt::tcXXX functions to avoid code duplication.

[kparzysz]

Yeah, there is no need for it right now. I was just curious about this kind of approach.

I can keep this as a patch here in case this issue comes back later.

[craig.topper]

Can we go ahead and add getHighestLane to the existing class to hide the Log2_32? Maybe getNumLanes as well.

[kparzysz]

Done in r308655 and r308658.

[hahmed]

I m working on huge hardware and I need this patch to work. When I tested this for N=128 I am getting error like "Must be a leaf subregister".

[craig.topper]

include/llvm/MC/LaneBitmask.h

149

I think this leaves all the other entries in T as garbage. This could explain the error hameeza is getting.

Try changing this to

Type T = {};

[kparzysz]

include/llvm/MC/LaneBitmask.h

149

Good catch.

Btw, feel free to reinstate yourself as a reviewer if you feel so inclined...

include/llvm/MC/LaneBitmask.h

 ///
 ///   (getSubRegIndexLaneMask(A) & getSubRegIndexLaneMask(B)) != 0
 
 #ifndef LLVM_MC_LANEBITMASK_H
 #define LLVM_MC_LANEBITMASK_H
 
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/Printable.h"
 #include "llvm/Support/raw_ostream.h"
+#include <array>
 
 namespace llvm {
 
+  struct LaneBitmask;
+  static LLVM_ATTRIBUTE_UNUSED Printable PrintLaneMask(LaneBitmask);
+  static LLVM_ATTRIBUTE_UNUSED Printable PrintLaneMaskAsInitList(LaneBitmask);
+
   struct LaneBitmask {
     // When changing the underlying type, change the format string as well.
-    using Type = unsigned;
-    enum : unsigned { BitWidth = 8*sizeof(Type) };
+    static const unsigned N = 1;
+    using Type = std::array<unsigned, N>;
+    enum : unsigned { BitWidth = 8*N*sizeof(unsigned) };
     constexpr static const char *const FormatStr = "%08X";
 
     constexpr LaneBitmask() = default;
     explicit constexpr LaneBitmask(Type V) : Mask(V) {}
 
-    constexpr bool operator== (LaneBitmask M) const { return Mask == M.Mask; }
-    constexpr bool operator!= (LaneBitmask M) const { return Mask != M.Mask; }
-    constexpr bool operator< (LaneBitmask M)  const { return Mask < M.Mask; }
-    constexpr bool none() const { return Mask == 0; }
-    constexpr bool any()  const { return Mask != 0; }
-    constexpr bool all()  const { return ~Mask == 0; }
-
-    constexpr LaneBitmask operator~() const {
-      return LaneBitmask(~Mask);
-    }
-    constexpr LaneBitmask operator|(LaneBitmask M) const {
-      return LaneBitmask(Mask | M.Mask);
-    }
-    constexpr LaneBitmask operator&(LaneBitmask M) const {
-      return LaneBitmask(Mask & M.Mask);
+    bool operator== (LaneBitmask M) const { return Mask == M.Mask; }
+    bool operator!= (LaneBitmask M) const { return Mask != M.Mask; }
+    bool operator< (LaneBitmask M)  const { return Mask < M.Mask; }
+    bool none() const {
+      for (unsigned I = 0; I != N; ++I)
+        if (Mask[I] != 0)
+          return false;
+      return true;
+    }
+    bool any() const {
+      for (unsigned I = 0; I != N; ++I)
+        if (Mask[I] != 0)
+          return true;
+      return false;
+    }
+    bool all() const {
+      for (unsigned I = 0; I != N; ++I)
+        if (Mask[I] != ~0u)
+          return false;
+      return true;
+    }
+
+    LaneBitmask operator~() const {
+      Type T;
+      for (unsigned I = 0; I != N; ++I)
+        T[I] = ~Mask[I];
+      return LaneBitmask(T);
+    }
+    LaneBitmask operator|(LaneBitmask M) const {
+      Type T;
+      for (unsigned I = 0; I != N; ++I)
+        T[I] = Mask[I] | M.Mask[I];
+      return LaneBitmask(T);
+    }
+    LaneBitmask operator&(LaneBitmask M) const {
+      Type T;
+      for (unsigned I = 0; I != N; ++I)
+        T[I] = Mask[I] & M.Mask[I];
+      return LaneBitmask(T);
     }
     LaneBitmask &operator|=(LaneBitmask M) {
-      Mask |= M.Mask;
+      for (unsigned I = 0; I != N; ++I)
+        Mask[I] |= M.Mask[I];
       return *this;
     }
     LaneBitmask &operator&=(LaneBitmask M) {
-      Mask &= M.Mask;
+      for (unsigned I = 0; I != N; ++I)
+        Mask[I] &= M.Mask[I];
+      return *this;
+    }
+
+    LaneBitmask rol(unsigned S) const {
+      if (S == 0)
         return *this;
+      Type T;
+
+      // Rotate words first.
+      unsigned W = S/32;
+      for (unsigned I = W; I != N; ++I)
+        T[I-W] = Mask[I];
+      for (unsigned I = 0; I != W; ++I)
+        T[I+W] = Mask[I];
+
+      S = S % 32;
+      if (S != 0) {
+        // Rotate bits.
+        unsigned M0 = T[0];
+        for (unsigned I = 0; I != N-1; ++I)
+          T[I] = (T[I] << S) | (T[I+1] >> (32-S));
+        T[N-1] = (T[N-1] << S) | (M0 >> (32-S));
       }
 
-    constexpr Type getAsInteger() const { return Mask; }
+      return LaneBitmask(T);
+    }
 
     unsigned getNumLanes() const {
-      return countPopulation(Mask);
+      unsigned S = 0;
+      for (unsigned M : Mask)
+        S += countPopulation(M);
+      return S;
     }
     unsigned getHighestLane() const {
-      return Log2_32(Mask);
+      for (unsigned I = N; I != 0; --I) {
+        if (Mask[I-1] == 0)
+          continue;
+        return Log2_32(Mask[I-1]) + 8*sizeof(unsigned)*(I-1);
+      }
+      return -1u;
     }
 
-    static constexpr LaneBitmask getNone() { return LaneBitmask(0); }
-    static constexpr LaneBitmask getAll() { return ~LaneBitmask(0); }
-    static constexpr LaneBitmask getLane(unsigned Lane) {
-      return LaneBitmask(Type(1) << Lane);
+    static LaneBitmask getNone() { return LaneBitmask(); }
+    static LaneBitmask getAll()  { return ~LaneBitmask(); }
+    static LaneBitmask getLane(unsigned Lane) {
+      Type T;
+      T[Lane / 32] = 1u << (Lane % 32);
+      return LaneBitmask(T);
     }
 
   private:
-    Type Mask = 0;
+    friend Printable PrintLaneMask(LaneBitmask LaneMask);
+    friend Printable PrintLaneMaskAsInitList(LaneBitmask LaneMask);
+    Type Mask = {{0}};
   };
 
-  /// Create Printable object to print LaneBitmasks on a \ref raw_ostream.
-  inline Printable PrintLaneMask(LaneBitmask LaneMask) {
+  /// Create Printable objects to print LaneBitmasks on a \ref raw_ostream.
+  static LLVM_ATTRIBUTE_UNUSED Printable PrintLaneMask(LaneBitmask LaneMask) {
     return Printable([LaneMask](raw_ostream &OS) {
-      OS << format(LaneBitmask::FormatStr, LaneMask.getAsInteger());
+      for (unsigned I = LaneBitmask::N; I != 0; --I)
+        OS << format(LaneBitmask::FormatStr, LaneMask.Mask[I-1]);
+    });
+  }
+
+  static LLVM_ATTRIBUTE_UNUSED Printable
+  PrintLaneMaskAsInitList(LaneBitmask LaneMask) {
+    return Printable([LaneMask](raw_ostream &OS) {
+      OS << "{{";
+      for (unsigned I = 0; I != LaneBitmask::N; ++I) {
+        if (I != 0)
+          OS << ',';
+        OS << "0x" << format(LaneBitmask::FormatStr, LaneMask.Mask[I]);
+      }
+      OS << "}}";
     });
   }
 
 } // end namespace llvm
 
 #endif // LLVM_MC_LANEBITMASK_H

lib/CodeGen/MIRParser/MIParser.cpp

if (parseNamedRegister(Reg))
       return true;
     lex();
     LaneBitmask Mask = LaneBitmask::getAll();
     if (consumeIfPresent(MIToken::colon)) {
       // Parse lane mask.
       if (Token.isNot(MIToken::IntegerLiteral) &&
           Token.isNot(MIToken::HexLiteral))
         return error("expected a lane mask");
-      static_assert(sizeof(LaneBitmask::Type) == sizeof(unsigned),
-                    "Use correct get-function for lane mask");
-      LaneBitmask::Type V;
+      unsigned V;
       if (getUnsigned(V))
         return error("invalid lane mask value");
-      Mask = LaneBitmask(V);
+      Mask = LaneBitmask({{V}});
       lex();
     }
     MBB.addLiveIn(Reg, Mask);
   } while (consumeIfPresent(MIToken::comma));
   return false;
 }
 
 bool MIParser::parseBasicBlockSuccessors(MachineBasicBlock &MBB) {

utils/TableGen/RegisterInfoEmitter.cpp

DiffVec &diffEncode(DiffVec &V, unsigned InitVal, Iter Begin, Iter End) {
   return V;
 }
 
 static void printDiff16(raw_ostream &OS, uint16_t Val) {
   OS << Val;
 }
 
 static void printMask(raw_ostream &OS, LaneBitmask Val) {
-  OS << "LaneBitmask(0x" << PrintLaneMask(Val) << ')';
+  OS << "LaneBitmask{" << PrintLaneMaskAsInitList(Val) << '}';
 }
 
 // Try to combine Idx's compose map into Vec if it is compatible.
 // Return false if it's not possible.
 static bool combine(const CodeGenSubRegIndex *Idx,
                     SmallVectorImpl<CodeGenSubRegIndex*> &Vec) {
   const CodeGenSubRegIndex::CompMap &Map = Idx->getComposites();
   for (const auto &I : Map) {
RegisterInfoEmitter::emitComposeSubRegIndexLaneMask(raw_ostream &OS,
   OS << "  };\n\n";
 
   OS << "LaneBitmask " << ClName
      << "::composeSubRegIndexLaneMaskImpl(unsigned IdxA, LaneBitmask LaneMask)"
         " const {\n"
         "  --IdxA; assert(IdxA < " << SubRegIndices.size()
      << " && \"Subregister index out of bounds\");\n"
         "  LaneBitmask Result;\n"
-        "  for (const MaskRolOp *Ops = CompositeSequences[IdxA]; Ops->Mask.any(); ++Ops) {\n"
-        "    LaneBitmask::Type M = LaneMask.getAsInteger() & Ops->Mask.getAsInteger();\n"
-        "    if (unsigned S = Ops->RotateLeft)\n"
-        "      Result |= LaneBitmask((M << S) | (M >> (LaneBitmask::BitWidth - S)));\n"
-        "    else\n"
-        "      Result |= LaneBitmask(M);\n"
-        "  }\n"
+        "  for (const MaskRolOp *Ops = CompositeSequences[IdxA]; Ops->Mask.any(); ++Ops)\n"
+        "    Result |= (LaneMask & Ops->Mask).rol(Ops->RotateLeft);\n"
         "  return Result;\n"
         "}\n\n";
 
   OS << "LaneBitmask " << ClName
      << "::reverseComposeSubRegIndexLaneMaskImpl(unsigned IdxA, "
         " LaneBitmask LaneMask) const {\n"
         "  LaneMask &= getSubRegIndexLaneMask(IdxA);\n"
         "  --IdxA; assert(IdxA < " << SubRegIndices.size()
      << " && \"Subregister index out of bounds\");\n"
         "  LaneBitmask Result;\n"
-        "  for (const MaskRolOp *Ops = CompositeSequences[IdxA]; Ops->Mask.any(); ++Ops) {\n"
-        "    LaneBitmask::Type M = LaneMask.getAsInteger();\n"
-        "    if (unsigned S = Ops->RotateLeft)\n"
-        "      Result |= LaneBitmask((M >> S) | (M << (LaneBitmask::BitWidth - S)));\n"
-        "    else\n"
-        "      Result |= LaneBitmask(M);\n"
-        "  }\n"
+        "  for (const MaskRolOp *Ops = CompositeSequences[IdxA]; Ops->Mask.any(); ++Ops)\n"
+        "    Result |= LaneMask.rol(LaneBitmask::BitWidth - Ops->RotateLeft);\n"
         "  return Result;\n"
         "}\n\n";
 }
 
 //
 // runMCDesc - Print out MC register descriptions.
 //
 void