[GlobalISel][Legalizer] LegalizerInfo verifier: checking that legalization rules cover all type indices

[rtereshin]

Summary

This patch adds a simple verifier that tracks type indices being touched by legalization rules' builders.

Every target will now have an opportunity to call LegalizerInfo::verify(...) at the end of its derived LegalizerInfo's constructor and check there are no obvious mistakes like checking only first type for an opcode that has more than one type index and therefore implicitly declaring any type for the second (and higher) type index legal.

The check is only ran in assert builds and should have very minor performance impact in assert builds and none in release builds.

This patch also doesn't make the verification errors fatal, only produces an error message, there is a follow up patch that does.

This is inspired by the discussion at https://reviews.llvm.org/D44704, please take a look there for more info on motivation.

This patch includes 2 commits:

the first is described above, it does not add LegalizerInfo::verify(...) calls to target-specific legalizers;

the second one has the following message:

[GlobalISel][AArch64] LegalizerInfo verifier: Adding LegalizerInfo::verify(...) call w/o fixing bugs
 
This is to make it clear what kind of bugs the LegalizerInfo::verifier
is able to catch and test its output

I also have an NFC commit planned to get in before this patch with the following commit message:

[GlobalISel][Legalizer] LegalizerInfo NFC, mostly reducing LegalizeRuleSet's methods' inter-dependecies

Making LegalizeRuleSet's implementation a little more dumb and
straightforward to make it easier to read and change, in particular in
order to add the initial version of LegalizerInfo verifier

[rtereshin]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

371 ↗

(On Diff #144809)

"Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp."

Greenspun's tenth rule of programming. 1993

[qcolombet]

Couple of nits on the tests.

test/CodeGen/AArch64/GlobalISel/legalize-inttoptr-xfail-1.mir

2 ↗

(On Diff #144809)

Could you add a comment explaining what you are testing in this test case?
Basically why is it useful? :)

Shouldn't we run not llc?

test/CodeGen/AArch64/GlobalISel/legalize-inttoptr-xfail-2.mir

2 ↗

(On Diff #144809)

Ditto.

[rtereshin]

test/CodeGen/AArch64/GlobalISel/legalize-inttoptr-xfail-1.mir

2 ↗

(On Diff #144809)

It's useful because it makes it obvious what kind of bugs we're missing w/o some kind of validation for LegalizerInfo. I guess I should add a comment saying exactly that :)

And the test passes, that's the point. So no not llc. Or you want not llc and XFAIL both in the same file?

[rtereshin]

test/CodeGen/AArch64/GlobalISel/legalize-inttoptr-xfail-2.mir

2 ↗

(On Diff #144809)

I think I'm going to put a not llc in the follow up (https://reviews.llvm.org/D46414), and then make these tests here in his patch exactly the same, but with XFAIL. And put the comment as suggested above. That would probably make most sense.

[rtereshin]

Updated the xfail tests to make their purpose clearer.

[rtereshin]

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

99 ↗

(On Diff #145130)

@qcolombet
+ @dsanders

I'll update the tests as requested in https://reviews.llvm.org/D46339 in a bit, in the meantime, I'm wondering, if it makes sense to check that we don't cover more type indices than there is as well, not just less.

It looks like in practice such mistakes are much less common, also, checking more type indices then needed fails much easier on an assertion while accessing an out of bounds item of the LegalityQuery::Types ArrayRef anyway. However, such a check is much more dynamic in a sense that it will only happen if there is a test that triggers a creation of such a query, while the verification proposed here despite not being strictly speaking static still catches issues as soon as a legalizer for a particular target is instantiated, so in practice, any test suffices.

What do you think?

Also, what do you think on the idea in general? I'm not particularly insisting that this patch is a good thing.

[rtereshin]

Adding comments to the tests as requested.

[rtereshin]

Removing -simplify-mir command line options from run-lines.

@qcolombet Is this one good to go as well as the follow up or not quite?

Thanks for looking into this!

Roman

[rtereshin]

ping

[rtereshin]

ping

[aemerson]

Overall I'm in favour of this change, so LGTM.

lib/CodeGen/GlobalISel/LegalizerInfo.cpp

553 ↗

(On Diff #146424)

This will need to be LLVM_DEBUG now I think.

llvm/trunk/include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

LegalizeRuleSet &actionFor(LegalizeAction Action,
                              std::initializer_list<LLT> Types,
                              LegalizeMutation Mutation) {
     using namespace LegalityPredicates;
     return actionIf(Action, typeInSet(0, Types), Mutation);
   }
   /// Use the given action when type indexes 0 and 1 is any type pair in the
   /// given list.
   /// Action should not be an action that requires mutation.
-  LegalizeRuleSet &
-  actionFor(LegalizeAction Action,
+  LegalizeRuleSet &actionFor(LegalizeAction Action,
                              std::initializer_list<std::pair<LLT, LLT>> Types) {
     using namespace LegalityPredicates;
     return actionIf(Action, typePairInSet(0, 1, Types));
   }
   /// Use the given action when type indexes 0 and 1 is any type pair in the
   /// given list.
   /// Action should be an action that requires mutation.
   LegalizeRuleSet &actionFor(LegalizeAction Action,
                              std::initializer_list<std::pair<LLT, LLT>> Types,
                              LegalizeMutation Mutation) {
     using namespace LegalityPredicates;
     return actionIf(Action, typePairInSet(0, 1, Types), Mutation);
   }
   /// Use the given action 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.
   /// Action should not be an action that requires mutation.
   LegalizeRuleSet &actionForCartesianProduct(LegalizeAction Action,
                                              std::initializer_list<LLT> Types) {
     using namespace LegalityPredicates;
     return actionIf(Action, all(typeInSet(0, Types), typeInSet(1, Types)));
   }
-  /// Use the given action when type indexes 0 and 1 are both their respective
-  /// lists.
+  /// Use the given action when type indexes 0 and 1 are both in their
+  /// respective lists.
   /// That is, the type pair is in the cartesian product of the lists
   /// Action should not be an action that requires mutation.
   LegalizeRuleSet &
   actionForCartesianProduct(LegalizeAction Action,
                             std::initializer_list<LLT> Types0,
                             std::initializer_list<LLT> Types1) {
     using namespace LegalityPredicates;
     return actionIf(Action, all(typeInSet(0, Types0), typeInSet(1, Types1)));
public:
   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) {
-    return legalIf(LegalityPredicates::typePairAndMemSizeInSet(
+    return actionIf(LegalizeAction::Legal,
+                    LegalityPredicates::typePairAndMemSizeInSet(
                         0, 1, /*MMOIdx*/ 0, TypesAndMemSize));
   }
   /// 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.
   LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types0,
                                             std::initializer_list<LLT> Types1) {
     return actionForCartesianProduct(LegalizeAction::Legal, Types0, Types1);
   }
 
   /// The instruction is lowered.
   LegalizeRuleSet &lower() {
     using namespace LegalizeMutations;
-    return actionIf(LegalizeAction::Lower, always, changeTo(0, 0));
+    return actionIf(LegalizeAction::Lower, always);
   }
   /// The instruction is lowered if predicate is true. Keep type index 0 as the
   /// same type.
   LegalizeRuleSet &lowerIf(LegalityPredicate Predicate) {
     using namespace LegalizeMutations;
-    return actionIf(LegalizeAction::Lower, Predicate, changeTo(0, 0));
+    return actionIf(LegalizeAction::Lower, Predicate);
+  }
+  /// The instruction is lowered if predicate is true.
+  LegalizeRuleSet &lowerIf(LegalityPredicate Predicate,
+                           LegalizeMutation Mutation) {
+    return actionIf(LegalizeAction::Lower, Predicate, Mutation);
   }
   /// The instruction is lowered when type index 0 is any type in the given
   /// list. Keep type index 0 as the same type.
   LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types) {
-    using namespace LegalizeMutations;
-    return lowerFor(Types, changeTo(0, 0));
+    return actionFor(LegalizeAction::Lower, Types,
+                     LegalizeMutations::changeTo(0, 0));
   }
-  /// The instruction is lowered when type indexes 0 and 1 is any type pair in the
-  /// given list. Keep type index 0 as the same type.
-  LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
-    return lowerFor(Types, LegalizeMutations::changeTo(0, 0));
-  }
-  /// The instruction is lowered when type indexes 0 and 1 is any type pair in the
-  /// given list.
-  LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types,
+  /// The instruction is lowered when type index 0 is any type in the given
+  /// list.
+  LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types,
                             LegalizeMutation Mutation) {
     return actionFor(LegalizeAction::Lower, Types, Mutation);
   }
-  /// The instruction is lowered if predicate is true.
-  LegalizeRuleSet &lowerIf(LegalityPredicate Predicate,
-                           LegalizeMutation Mutation) {
-    return actionIf(LegalizeAction::Lower, Predicate, Mutation);
+  /// The instruction is lowered when type indexes 0 and 1 is any type pair in
+  /// the given list. Keep type index 0 as the same type.
+  LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
+    return actionFor(LegalizeAction::Lower, Types,
+                     LegalizeMutations::changeTo(0, 0));
   }
-  /// The instruction is lowered when type index 0 is any type in the given list.
-  LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types,
+  /// The instruction is lowered when type indexes 0 and 1 is any type pair in
+  /// the given list.
+  LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types,
                             LegalizeMutation Mutation) {
     return actionFor(LegalizeAction::Lower, Types, Mutation);
   }
 
   /// Like legalIf, but for the Libcall action.
   LegalizeRuleSet &libcallIf(LegalityPredicate Predicate) {
     return actionIf(LegalizeAction::Libcall, Predicate);
   }
public:
   LegalizeRuleSet &
   customForCartesianProduct(std::initializer_list<LLT> Types0,
                             std::initializer_list<LLT> Types1) {
     return actionForCartesianProduct(LegalizeAction::Custom, Types0, Types1);
   }
 
   /// Widen the scalar to the next power of two that is at least MinSize.
   /// No effect if the type is not a scalar or is a power of two.
-  LegalizeRuleSet &widenScalarToNextPow2(unsigned TypeIdx, unsigned MinSize = 0) {
+  LegalizeRuleSet &widenScalarToNextPow2(unsigned TypeIdx,
+                                         unsigned MinSize = 0) {
     using namespace LegalityPredicates;
-    return widenScalarIf(
-        sizeNotPow2(TypeIdx),
+    return actionIf(LegalizeAction::WidenScalar, sizeNotPow2(TypeIdx),
                     LegalizeMutations::widenScalarToNextPow2(TypeIdx, MinSize));
   }
 
   LegalizeRuleSet &narrowScalar(unsigned TypeIdx, LegalizeMutation Mutation) {
     using namespace LegalityPredicates;
-    return narrowScalarIf(isScalar(TypeIdx), Mutation);
+    return actionIf(LegalizeAction::NarrowScalar, isScalar(TypeIdx), Mutation);
   }
 
   /// Ensure the scalar is at least as wide as Ty.
   LegalizeRuleSet &minScalar(unsigned TypeIdx, const LLT &Ty) {
     using namespace LegalityPredicates;
     using namespace LegalizeMutations;
-    return widenScalarIf(narrowerThan(TypeIdx, Ty.getSizeInBits()),
-                         changeTo(TypeIdx, Ty));
+    return actionIf(LegalizeAction::WidenScalar,
+                    narrowerThan(TypeIdx, Ty.getSizeInBits()),
   }
 
   /// Ensure the scalar is at most as wide as Ty.
   LegalizeRuleSet &maxScalar(unsigned TypeIdx, const LLT &Ty) {
     using namespace LegalityPredicates;
     using namespace LegalizeMutations;
-    return narrowScalarIf(widerThan(TypeIdx, Ty.getSizeInBits()),
-                          changeTo(TypeIdx, Ty));
+    return actionIf(LegalizeAction::NarrowScalar,
+                    widerThan(TypeIdx, Ty.getSizeInBits()),
   }
 
   /// Conditionally limit the maximum size of the scalar.
   /// For example, when the maximum size of one type depends on the size of
   /// another such as extracting N bits from an M bit container.
-  LegalizeRuleSet &maxScalarIf(LegalityPredicate Predicate, unsigned TypeIdx, const LLT &Ty) {
+  LegalizeRuleSet &maxScalarIf(LegalityPredicate Predicate, unsigned TypeIdx,
+                               const LLT &Ty) {
     using namespace LegalityPredicates;
     using namespace LegalizeMutations;
-    return narrowScalarIf(
+    return actionIf(LegalizeAction::NarrowScalar,
                     [=](const LegalityQuery &Query) {
                       return widerThan(TypeIdx, Ty.getSizeInBits()) &&
                              Predicate(Query);
                     },
                     changeTo(TypeIdx, Ty));
   }
 
   /// Limit the range of scalar sizes to MinTy and MaxTy.
-  LegalizeRuleSet &clampScalar(unsigned TypeIdx, const LLT &MinTy, const LLT &MaxTy) {
+  LegalizeRuleSet &clampScalar(unsigned TypeIdx, const LLT &MinTy,
+                               const LLT &MaxTy) {
     assert(MinTy.isScalar() && MaxTy.isScalar() && "Expected scalar types");
-
-    return minScalar(TypeIdx, MinTy)
-        .maxScalar(TypeIdx, MaxTy);
+    return minScalar(TypeIdx, MinTy).maxScalar(TypeIdx, MaxTy);
   }
 
   /// Add more elements to the vector to reach the next power of two.
   /// No effect if the type is not a vector or the element count is a power of
   /// two.
   LegalizeRuleSet &moreElementsToNextPow2(unsigned TypeIdx) {
     using namespace LegalityPredicates;
-    return moreElementsIf(numElementsNotPow2(TypeIdx),
-                          LegalizeMutations::moreElementsToNextPow2(TypeIdx));
+    return actionIf(LegalizeAction::MoreElements, numElementsNotPow2(TypeIdx),
   }
 
   /// Limit the number of elements in EltTy vectors to at least MinElements.
   LegalizeRuleSet &clampMinNumElements(unsigned TypeIdx, const LLT &EltTy,
                                        unsigned MinElements) {
-    return moreElementsIf(
+    return actionIf(
+        LegalizeAction::MoreElements,
         [=](const LegalityQuery &Query) {
           LLT VecTy = Query.Types[TypeIdx];
           return VecTy.isVector() && VecTy.getElementType() == EltTy &&
                  VecTy.getNumElements() < MinElements;
         },
         [=](const LegalityQuery &Query) {
           LLT VecTy = Query.Types[TypeIdx];
           return std::make_pair(
               TypeIdx, LLT::vector(MinElements, VecTy.getScalarSizeInBits()));
         });
   }
   /// Limit the number of elements in EltTy vectors to at most MaxElements.
   LegalizeRuleSet &clampMaxNumElements(unsigned TypeIdx, const LLT &EltTy,
                                        unsigned MaxElements) {
-    return fewerElementsIf(
+    return actionIf(
+        LegalizeAction::FewerElements,
         [=](const LegalityQuery &Query) {
           LLT VecTy = Query.Types[TypeIdx];
           return VecTy.isVector() && VecTy.getElementType() == EltTy &&
                  VecTy.getNumElements() > MaxElements;
         },
         [=](const LegalityQuery &Query) {
           LLT VecTy = Query.Types[TypeIdx];
           return std::make_pair(