GlobalISel: Add alignment to LegalityQuery MMOs

[arsenm]

Summary

This allows targets to specify the minimum alignment required for the
load/store.

[Petar.Avramovic]

Hi, this rule will be very useful for mips32r5 that only supports naturally aligned loads and stores.
However, could we have additional structure named TypeMemAndAlignDesc (or something more appropriate) and rule that uses this structure named legalForTypesWithMemSizeAndAlign instead of changing already existing ones.
This would leave TypePairAndMemSize and typePairAndMemSizeInSet to be used as is, since alignment is not considered on some targets/subtargets (like mips32r6). There are rules that do not take memsize into account (like LegalFor or legalForCartesianProduct).

[arsenm]

In D57449#1377155, @Petar.Avramovic wrote:

Hi, this rule will be very useful for mips32r5 that only supports naturally aligned loads and stores.
However, could we have additional structure named TypeMemAndAlignDesc (or something more appropriate) and rule that uses this structure named legalForTypesWithMemSizeAndAlign instead of changing already existing ones.
This would leave TypePairAndMemSize and typePairAndMemSizeInSet to be used as is, since alignment is not considered on some targets/subtargets (like mips32r6). There are rules that do not take memsize into account (like LegalFor or legalForCartesianProduct).

I would think having fewer versions with all the necessary information would be better. The memory instructions are already special since they care about something besides the operand types. Also, this isn't the only addition I want to make here. I'll probably want to add the MMO flags here at some point, and wouldn't want to introduce a 3rd set of these

[Petar.Avramovic]

OK.

[arsenm]

ping

[aemerson]

@dsanders does this look ok to you?

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

180

This isCompatible relation isn't commutative, so it would be good to make it clear here what it actually means for A.isCompatible(B) to be true.

[dsanders]

In D57449#1388378, @aemerson wrote:

@dsanders does this look ok to you?

This looks sensible to me. I agree with adding it to the existing type as most targets will want to be checking alignment here and the few that don't can just check against alignment 1.

From my side, there's just the one nit that Amara didn't already raise which is the truncation of the getAlignment() result. We should probably just store the uint64_t (and hope the optimizer is smart enough to inline it into the lambda). If we're going to do the truncate we should have an assert guard against overflow.

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

428

Why the static cast?

[arsenm]

I'm not sure why the MMO alignment is uint64_t in the first place. The maximum supported alignment is 1 << 29 (which I guess when converted to bits is 1 too many for uint32)

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

428

LegalizerInfo.cpp:429:10: error: non-constant-expression cannot be narrowed from type 'unsigned long long' to 'uint32_t' (aka 'unsigned int') in initializer list [-Wc++11-narrowing]

MMO->getAlignment() * 8});
^~~~~~~~~~~~~~~~~~~~~~~

../lib/CodeGen/GlobalISel/LegalizerInfo.cpp:429:10: note: insert an explicit cast to silence this issue

MMO->getAlignment() * 8});
^~~~~~~~~~~~~~~~~~~~~~~
static_cast<uint32_t>( )

[dsanders]

In D57449#1389860, @arsenm wrote:

I'm not sure why the MMO alignment is uint64_t in the first place. The maximum supported alignment is 1 << 29 (which I guess when converted to bits is 1 too many for uint32)

Hmm, 1 << 29 is in range for both uint32_t and int32_t so it's presumably just an overly large return type. Fair enough, I think it would be good to fix the oversized return value so that people don't have to silence these warnings but that's not for this patch.

[arsenm]

Add comment, make sure the maximum alignment works.

Size probably doesn't need to be 64-bits since LLT only supports 16-bits

[dsanders]

LGTM

[arsenm]

r354071

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

 /// For efficiency, it doesn't make a copy of Types so care must be taken not
 /// to free it before using the query.
 struct LegalityQuery {
   unsigned Opcode;
   ArrayRef<LLT> Types;
 
   struct MemDesc {
     uint64_t SizeInBits;
+    uint64_t AlignInBits;
     AtomicOrdering Ordering;
   };
 
   /// Operations which require memory can use this to place requirements on the
   /// memory type for each MMO.
   ArrayRef<MemDesc> MMODescrs;
 
   constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types,
struct LegalizeActionStep {
   }
 };
 
 using LegalityPredicate = std::function<bool (const LegalityQuery &)>;
 using LegalizeMutation =
     std::function<std::pair<unsigned, LLT>(const LegalityQuery &)>;
 
 namespace LegalityPredicates {
-struct TypePairAndMemSize {
+struct TypePairAndMemDesc {
   LLT Type0;
   LLT Type1;
   uint64_t MemSize;
+  uint64_t Align;
 
-  bool operator==(const TypePairAndMemSize &Other) const {
+  bool operator==(const TypePairAndMemDesc &Other) const {
     return Type0 == Other.Type0 && Type1 == Other.Type1 &&
+           Align == Other.Align &&
+           MemSize == Other.MemSize;
+  }
+
+  /// \returns true if this memory access is legal with for the acecss described
+  /// by \p Other (The alignment is sufficient for the size and result type).
+  bool isCompatible(const TypePairAndMemDesc &Other) const {
+    return Type0 == Other.Type0 && Type1 == Other.Type1 &&
+           Align >= Other.Align &&
            MemSize == Other.MemSize;
   }
 };
 
 /// True iff P0 and P1 are true.
 template<typename Predicate>
 Predicate all(Predicate P0, Predicate P1) {
   return [=](const LegalityQuery &Query) {
LegalityPredicate typeInSet(unsigned TypeIdx,
                             std::initializer_list<LLT> TypesInit);
 /// True iff the given types for the given pair of type indexes is one of the
 /// specified type pairs.
 LegalityPredicate
 typePairInSet(unsigned TypeIdx0, unsigned TypeIdx1,
               std::initializer_list<std::pair<LLT, LLT>> TypesInit);
 /// True iff the given types for the given pair of type indexes is one of the
 /// specified type pairs.
-LegalityPredicate typePairAndMemSizeInSet(
+LegalityPredicate typePairAndMemDescInSet(
     unsigned TypeIdx0, unsigned TypeIdx1, unsigned MMOIdx,
-    std::initializer_list<TypePairAndMemSize> TypesAndMemSizeInit);
+    std::initializer_list<TypePairAndMemDesc> TypesAndMemDescInit);
 /// True iff the specified type index is a scalar.
 LegalityPredicate isScalar(unsigned TypeIdx);
 /// True iff the specified type index is a vector.
 LegalityPredicate isVector(unsigned TypeIdx);
 /// True iff the specified type index is a pointer (with any address space).
 LegalityPredicate isPointer(unsigned TypeIdx);
 /// True iff the specified type index is a pointer with the specified address
 /// space.
LegalizeRuleSet &legalFor(std::initializer_list<LLT> Types) {
     return actionFor(LegalizeAction::Legal, Types);
   }
   /// The instruction is legal when type indexes 0 and 1 is any type pair in the
   /// given list.
   LegalizeRuleSet &legalFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
     return actionFor(LegalizeAction::Legal, Types);
   }
   /// The instruction is legal when type indexes 0 and 1 along with the memory
-  /// size is any type and size tuple in the given list.
-  LegalizeRuleSet &legalForTypesWithMemSize(
-      std::initializer_list<LegalityPredicates::TypePairAndMemSize>
-          TypesAndMemSize) {
+  /// size and minimum alignment is any type and size tuple in the given list.
+  LegalizeRuleSet &legalForTypesWithMemDesc(
+      std::initializer_list<LegalityPredicates::TypePairAndMemDesc>
+          TypesAndMemDesc) {
     return actionIf(LegalizeAction::Legal,
-                    LegalityPredicates::typePairAndMemSizeInSet(
-                        typeIdx(0), typeIdx(1), /*MMOIdx*/ 0, TypesAndMemSize));
+                    LegalityPredicates::typePairAndMemDescInSet(
+                        typeIdx(0), typeIdx(1), /*MMOIdx*/ 0, TypesAndMemDesc));
   }
   /// The instruction is legal when type indexes 0 and 1 are both in the given
   /// list. That is, the type pair is in the cartesian product of the list.
   LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types) {
     return actionForCartesianProduct(LegalizeAction::Legal, Types);
   }
   /// The instruction is legal when type indexes 0 and 1 are both their
   /// respective lists.

lib/CodeGen/GlobalISel/LegalityPredicates.cpp

LegalityPredicate LegalityPredicates::typePairInSet(
     std::initializer_list<std::pair<LLT, LLT>> TypesInit) {
   SmallVector<std::pair<LLT, LLT>, 4> Types = TypesInit;
   return [=](const LegalityQuery &Query) {
     std::pair<LLT, LLT> Match = {Query.Types[TypeIdx0], Query.Types[TypeIdx1]};
     return std::find(Types.begin(), Types.end(), Match) != Types.end();
   };
 }
 
-LegalityPredicate LegalityPredicates::typePairAndMemSizeInSet(
+LegalityPredicate LegalityPredicates::typePairAndMemDescInSet(
     unsigned TypeIdx0, unsigned TypeIdx1, unsigned MMOIdx,
-    std::initializer_list<TypePairAndMemSize> TypesAndMemSizeInit) {
-  SmallVector<TypePairAndMemSize, 4> TypesAndMemSize = TypesAndMemSizeInit;
+    std::initializer_list<TypePairAndMemDesc> TypesAndMemDescInit) {
+  SmallVector<TypePairAndMemDesc, 4> TypesAndMemDesc = TypesAndMemDescInit;
   return [=](const LegalityQuery &Query) {
-    TypePairAndMemSize Match = {Query.Types[TypeIdx0], Query.Types[TypeIdx1],
-                                Query.MMODescrs[MMOIdx].SizeInBits};
-    return std::find(TypesAndMemSize.begin(), TypesAndMemSize.end(), Match) !=
-           TypesAndMemSize.end();
+    TypePairAndMemDesc Match = {Query.Types[TypeIdx0], Query.Types[TypeIdx1],
+                                Query.MMODescrs[MMOIdx].SizeInBits,
+                                Query.MMODescrs[MMOIdx].AlignInBits};
+    return std::find_if(
+      TypesAndMemDesc.begin(), TypesAndMemDesc.end(),
+      [=](const TypePairAndMemDesc &Entry) ->bool {
+        return Match.isCompatible(Entry);
+      }) != TypesAndMemDesc.end();
   };
 }
 
 LegalityPredicate LegalityPredicates::isScalar(unsigned TypeIdx) {
   return [=](const LegalityQuery &Query) {
     return Query.Types[TypeIdx].isScalar();
   };
 }

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
     SeenTypes.set(TypeIdx);
 
     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
     Types.push_back(Ty);
   }
 
   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
   for (const auto &MMO : MI.memoperands())
-    MemDescrs.push_back(
-        {MMO->getSize() /* in bytes */ * 8, MMO->getOrdering()});
+    MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
+                         8 * MMO->getAlignment(),
+                         MMO->getOrdering()});
 
   return getAction({MI.getOpcode(), Types, MemDescrs});
 }
 
 bool LegalizerInfo::isLegal(const MachineInstr &MI,
                             const MachineRegisterInfo &MRI) const {
   return getAction(MI, MRI).Action == Legal;
 }

lib/Target/AArch64/AArch64LegalizerInfo.cpp

getActionDefinitionsBuilder(G_EXTRACT)
       })
       .clampScalar(1, s32, s64)
       .widenScalarToNextPow2(1)
       .maxScalarIf(typeInSet(1, {s32}), 0, s16)
       .maxScalarIf(typeInSet(1, {s64}), 0, s32)
       .widenScalarToNextPow2(0);
 
   getActionDefinitionsBuilder({G_SEXTLOAD, G_ZEXTLOAD})
-      .legalForTypesWithMemSize({{s32, p0, 8},
-                                 {s32, p0, 16},
-                                 {s32, p0, 32},
-                                 {s64, p0, 64},
-                                 {p0, p0, 64},
-                                 {v2s32, p0, 64}})
+      .legalForTypesWithMemDesc({{s32, p0, 8, 8},
+                                 {s32, p0, 16, 8},
+                                 {s32, p0, 32, 8},
+                                 {s64, p0, 64, 8},
+                                 {p0, p0, 64, 8},
+                                 {v2s32, p0, 64, 8}})
       .clampScalar(0, s32, s64)
       .widenScalarToNextPow2(0)
       // TODO: We could support sum-of-pow2's but the lowering code doesn't know
       //       how to do that yet.
       .unsupportedIfMemSizeNotPow2()
       // Lower anything left over into G_*EXT and G_LOAD
       .lower();
 
   getActionDefinitionsBuilder(G_LOAD)
-      .legalForTypesWithMemSize({{s8, p0, 8},
-                                 {s16, p0, 16},
-                                 {s32, p0, 32},
-                                 {s64, p0, 64},
-                                 {p0, p0, 64},
-                                 {v2s32, p0, 64}})
+      .legalForTypesWithMemDesc({{s8, p0, 8, 8},
+                                 {s16, p0, 16, 8},
+                                 {s32, p0, 32, 8},
+                                 {s64, p0, 64, 8},
+                                 {p0, p0, 64, 8},
+                                 {v2s32, p0, 64, 8}})
       // These extends are also legal
-      .legalForTypesWithMemSize({{s32, p0, 8},
-                                 {s32, p0, 16}})
+      .legalForTypesWithMemDesc({{s32, p0, 8, 8},
+                                 {s32, p0, 16, 8}})
       .clampScalar(0, s8, s64)
       .widenScalarToNextPow2(0)
       // TODO: We could support sum-of-pow2's but the lowering code doesn't know
       //       how to do that yet.
       .unsupportedIfMemSizeNotPow2()
       // Lower any any-extending loads left into G_ANYEXT and G_LOAD
       .lowerIf([=](const LegalityQuery &Query) {
         return Query.Types[0].getSizeInBits() != Query.MMODescrs[0].SizeInBits;
       })
       .clampMaxNumElements(0, s32, 2)
       .clampMaxNumElements(0, s64, 1);
 
   getActionDefinitionsBuilder(G_STORE)
-      .legalForTypesWithMemSize({{s8, p0, 8},
-                                 {s16, p0, 16},
-                                 {s32, p0, 32},
-                                 {s64, p0, 64},
-                                 {p0, p0, 64},
-                                 {v2s32, p0, 64}})
+      .legalForTypesWithMemDesc({{s8, p0, 8, 8},
+                                 {s16, p0, 16, 8},
+                                 {s32, p0, 32, 8},
+                                 {s64, p0, 64, 8},
+                                 {p0, p0, 64, 8},
+                                 {v2s32, p0, 64, 8}})
       .clampScalar(0, s8, s64)
       .widenScalarToNextPow2(0)
       // TODO: We could support sum-of-pow2's but the lowering code doesn't know
       //       how to do that yet.
       .unsupportedIfMemSizeNotPow2()
       .lowerIf([=](const LegalityQuery &Query) {
         return Query.Types[0].isScalar() &&
                Query.Types[0].getSizeInBits() != Query.MMODescrs[0].SizeInBits;

lib/Target/AMDGPU/AMDGPULegalizerInfo.cpp

.legalIf([=, &ST](const LegalityQuery &Query) {
           // TODO: constant loads
         default:
           return false;
         }
       })
     .clampScalar(0, S32, S64);
 
 
+  // FIXME: Handle alignment requirements.
   auto &ExtLoads = getActionDefinitionsBuilder({G_SEXTLOAD, G_ZEXTLOAD})
-    .legalForTypesWithMemSize({
-        {S32, GlobalPtr, 8},
-        {S32, GlobalPtr, 16},
-        {S32, LocalPtr, 8},
-        {S32, LocalPtr, 16},
-        {S32, PrivatePtr, 8},
-        {S32, PrivatePtr, 16}});
+    .legalForTypesWithMemDesc({
+        {S32, GlobalPtr, 8, 8},
+        {S32, GlobalPtr, 16, 8},
+        {S32, LocalPtr, 8, 8},
+        {S32, LocalPtr, 16, 8},
+        {S32, PrivatePtr, 8, 8},
+        {S32, PrivatePtr, 16, 8}});
   if (ST.hasFlatAddressSpace()) {
-    ExtLoads.legalForTypesWithMemSize({{S32, FlatPtr, 8},
-                                       {S32, FlatPtr, 16}});
+    ExtLoads.legalForTypesWithMemDesc({{S32, FlatPtr, 8, 8},
+                                       {S32, FlatPtr, 16, 8}});
   }
 
   ExtLoads.clampScalar(0, S32, S32)
           .widenScalarToNextPow2(0)
           .unsupportedIfMemSizeNotPow2()
           .lower();
 
   auto &Atomics = getActionDefinitionsBuilder(

lib/Target/ARM/ARMLegalizerInfo.cpp

ARMLegalizerInfo::ARMLegalizerInfo(const ARMSubtarget &ST) {
   getActionDefinitionsBuilder(G_ICMP)
       .legalForCartesianProduct({s1}, {s32, p0})
       .minScalar(1, s32);
 
   // We're keeping these builders around because we'll want to add support for
   // floating point to them.
   auto &LoadStoreBuilder =
       getActionDefinitionsBuilder({G_LOAD, G_STORE})
-          .legalForTypesWithMemSize({
-              {s1, p0, 8},
-              {s8, p0, 8},
-              {s16, p0, 16},
-              {s32, p0, 32},
-              {p0, p0, 32}});
+          .legalForTypesWithMemDesc({
+              {s1, p0, 8, 8},
+              {s8, p0, 8, 8},
+              {s16, p0, 16, 8},
+              {s32, p0, 32, 8},
+              {p0, p0, 32, 8}});
 
   getActionDefinitionsBuilder(G_GEP).legalFor({{p0, s32}});
 
   if (ST.isThumb()) {
     // FIXME: merge with the code for non-Thumb.
     computeTables();
     verify(*ST.getInstrInfo());
     return;

lib/Target/Mips/MipsLegalizerInfo.cpp

MipsLegalizerInfo::MipsLegalizerInfo(const MipsSubtarget &ST) {
 
   getActionDefinitionsBuilder({G_UADDE, G_USUBO, G_USUBE})
       .lowerFor({{s32, s1}});
 
   getActionDefinitionsBuilder({G_LOAD, G_STORE})
       .legalForCartesianProduct({p0, s32}, {p0});
 
   getActionDefinitionsBuilder({G_ZEXTLOAD, G_SEXTLOAD})
-      .legalForTypesWithMemSize({{s32, p0, 8},
-                                 {s32, p0, 16}})
+    .legalForTypesWithMemDesc({{s32, p0, 8, 8},
+                               {s32, p0, 16, 8}})
       .minScalar(0, s32);
 
   getActionDefinitionsBuilder(G_SELECT)
       .legalForCartesianProduct({p0, s32}, {s32})
       .minScalar(0, s32)
       .minScalar(1, s32);
 
   getActionDefinitionsBuilder({G_AND, G_OR, G_XOR})

unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp

// Test widenScalarToNextPow2
     EXPECT_ACTION(WidenScalar, 0, s32, LegalityQuery(G_AND, {s5}));
     EXPECT_ACTION(WidenScalar, 0, s64, LegalityQuery(G_AND, {s33}));
 
     // Do nothing for vectors.
     EXPECT_ACTION(Unsupported, 0, LLT(), LegalityQuery(G_AND, {v2s5}));
     EXPECT_ACTION(Unsupported, 0, LLT(), LegalityQuery(G_AND, {v2s33}));
   }
 }
+
+TEST(LegalizerInfoTest, MMOAlignment) {
+  using namespace TargetOpcode;
+
+  const LLT s32 = LLT::scalar(32);
+  const LLT p0 = LLT::pointer(0, 64);
+
+  {
+    LegalizerInfo LI;
+    LI.getActionDefinitionsBuilder(G_LOAD)
+      .legalForTypesWithMemDesc({{s32, p0, 32, 32}});
+
+    LI.computeTables();
+
+    EXPECT_ACTION(Legal, 0, LLT(),
+                  LegalityQuery(G_LOAD, {s32, p0},
+                                LegalityQuery::MemDesc{
+                                  32, 32, AtomicOrdering::NotAtomic}));
+    EXPECT_ACTION(Unsupported, 0, LLT(),
+                  LegalityQuery(G_LOAD, {s32, p0},
+                                LegalityQuery::MemDesc{
+                                  32, 16, AtomicOrdering::NotAtomic }));
+    EXPECT_ACTION(Unsupported, 0, LLT(),
+                  LegalityQuery(G_LOAD, {s32, p0},
+                                LegalityQuery::MemDesc{
+                                  32, 8, AtomicOrdering::NotAtomic}));
+  }
+
+  // Test that the maximum supported alignment value isn't truncated
+  {
+    // Maximum IR defined alignment in bytes.
+    const uint64_t MaxAlignment = UINT64_C(1) << 29;
+    const uint64_t MaxAlignInBits = 8 * MaxAlignment;
+    LegalizerInfo LI;
+    LI.getActionDefinitionsBuilder(G_LOAD)
+      .legalForTypesWithMemDesc({{s32, p0, 32, MaxAlignInBits}});
+
+    LI.computeTables();
+
+    EXPECT_ACTION(Legal, 0, LLT(),
+                  LegalityQuery(G_LOAD, {s32, p0},
+                                LegalityQuery::MemDesc{32,
+                                    MaxAlignInBits, AtomicOrdering::NotAtomic}));
+    EXPECT_ACTION(Unsupported, 0, LLT(),
+                  LegalityQuery(G_LOAD, {s32, p0},
+                                LegalityQuery::MemDesc{
+                                  32, 8, AtomicOrdering::NotAtomic }));
+  }
+}