[globalisel] Introduce LegalityQuery to better encapsulate the legalizer decisions. NFC.

[dsanders]

Summary

getAction(const InstrAspect &) const breaks encapsulation by exposing
the smaller components that are used to decide how to legalize an
instruction.

This is a problem because we need to change the implementation of
LegalizerInfo so that it's able to describe particular type combinations
rather than just cartesian products of types.

For example, declaring the following

setAction({..., 0, s32}, Legal)
setAction({..., 0, s64}, Legal)
setAction({..., 1, s32}, Legal)
setAction({..., 1, s64}, Legal)

currently declares these type combinations as legal:

{s32, s32}
{s64, s32}
{s32, s64}
{s64, s64}

but we currently have no means to say that, for example, {s64, s32} is
not legal. Some operations such as G_INSERT/G_EXTRACT/G_MERGE_VALUES/
G_UNMERGE_VALUES has relationships between the types that are currently
described incorrectly.

Additionally, G_LOAD/G_STORE currently have no means to legalize non-atomics
differently to atomics. The necessary information is in the MMO but we have no
way to use this in the legalizer. Similarly, there is currently no way for the
register type and the memory type to differ so there is no way to cleanly
represent extending-load/truncating-store in a way that can't be broken by
optimizers (resulting in illegal MIR).

This patch introduces LegalityQuery which provides all the information
needed by the legalizer to make a decision on whether something is legal
and how to legalize it.

[bogner]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

273–276 ↗

(On Diff #130422)

The bit about returning a pair in the doc isn't accurate anymore.

Could we return a small pod struct with named fields instead of a tuple here? Tuples really don't have any advantage over simple structs in C++11 and later, IMO, and it's a lot harder to tell what's happening with them. I guess that would probably be a separate change, given that similar tuples are used elsewhere already.

[dsanders]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

273–276 ↗

(On Diff #130422)

The bit about returning a pair in the doc isn't accurate anymore.

Good point. I'll fix that

Could we return a small pod struct with named fields instead of a tuple here? Tuples really don't have any advantage over simple structs in C++11 and later, IMO, and it's a lot harder to tell what's happening with them. I guess that would probably be a separate change, given that similar tuples are used elsewhere already.

Sure. I went with a tuple since I was trying to bring it into line with the other getAction() below but it would be better to change both of them to a struct

[rovka]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

56 ↗

(On Diff #130422)

Is it really a good idea to store an ArrayRef in the long run?

[dsanders]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

56 ↗

(On Diff #130422)

This object is only needed for the duration of a single call to getAction() so there shouldn't be any problems with LegalityQuery::Types outliving the array used to initialize it.

[dsanders]

Change tuple to a struct
Update unit tests
Add comment explaining that LegalityQuery does not take a copy of the types array.

[reames]

Not really a qualified reviewer for this, but I'll comment this reads more cleanly to someone unfamiliar with the details of the code.

[bogner]

LGTM. I have a couple of style comments you can take or leave as you see fit.

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

62–63 ↗

(On Diff #130929)

Pretty sure there's no need to spell this out. For a struct/class with only public members and no constructor you can aggregate-initialize with an initializer-list.

130–133 ↗

(On Diff #130929)

I was going to say that we usually name the parameter RHS and do the std::tie(A, B) == std::tie(RHS.A, RHS.B) pattern here, but a quick look shows that we're not at all consistent about that, so I guess you can do whatever you think is clearest.

[dsanders]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

62–63 ↗

(On Diff #130929)

I've removed it from this one. The one in LegalizeActionStep seems to be necessary though. The unit tests don't build without it

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

bool tryCombineZExt(MachineInstr &MI,
                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
 
     if (MI.getOpcode() != TargetOpcode::G_ZEXT)
       return false;
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
                                            MI.getOperand(1).getReg(), MRI)) {
       unsigned DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
-      if (isInstUnsupported(TargetOpcode::G_AND, DstTy) ||
-          isInstUnsupported(TargetOpcode::G_CONSTANT, DstTy))
+      if (isInstUnsupported({TargetOpcode::G_AND, {DstTy}}) ||
+          isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
         return false;
       DEBUG(dbgs() << ".. Combine MI: " << MI;);
       Builder.setInstr(MI);
       unsigned ZExtSrc = MI.getOperand(1).getReg();
       LLT ZExtSrcTy = MRI.getType(ZExtSrc);
       APInt Mask = APInt::getAllOnesValue(ZExtSrcTy.getSizeInBits());
       auto MaskCstMIB = Builder.buildConstant(DstTy, Mask.getZExtValue());
       unsigned TruncSrc = DefMI->getOperand(1).getReg();
bool tryCombineSExt(MachineInstr &MI,
                       SmallVectorImpl<MachineInstr *> &DeadInsts) {
 
     if (MI.getOpcode() != TargetOpcode::G_SEXT)
       return false;
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_TRUNC,
                                            MI.getOperand(1).getReg(), MRI)) {
       unsigned DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
-      if (isInstUnsupported(TargetOpcode::G_SHL, DstTy) ||
-          isInstUnsupported(TargetOpcode::G_ASHR, DstTy) ||
-          isInstUnsupported(TargetOpcode::G_CONSTANT, DstTy))
+      if (isInstUnsupported({TargetOpcode::G_SHL, {DstTy}}) ||
+          isInstUnsupported({TargetOpcode::G_ASHR, {DstTy}}) ||
+          isInstUnsupported({TargetOpcode::G_CONSTANT, {DstTy}}))
         return false;
       DEBUG(dbgs() << ".. Combine MI: " << MI;);
       Builder.setInstr(MI);
       unsigned SExtSrc = MI.getOperand(1).getReg();
       LLT SExtSrcTy = MRI.getType(SExtSrc);
       unsigned SizeDiff = DstTy.getSizeInBits() - SExtSrcTy.getSizeInBits();
       auto SizeDiffMIB = Builder.buildConstant(DstTy, SizeDiff);
       unsigned TruncSrcReg = DefMI->getOperand(1).getReg();
bool tryFoldImplicitDef(MachineInstr &MI,
     if (Opcode != TargetOpcode::G_ANYEXT && Opcode != TargetOpcode::G_ZEXT &&
         Opcode != TargetOpcode::G_SEXT)
       return false;
 
     if (MachineInstr *DefMI = getOpcodeDef(TargetOpcode::G_IMPLICIT_DEF,
                                            MI.getOperand(1).getReg(), MRI)) {
       unsigned DstReg = MI.getOperand(0).getReg();
       LLT DstTy = MRI.getType(DstReg);
-      if (isInstUnsupported(TargetOpcode::G_IMPLICIT_DEF, DstTy))
+      if (isInstUnsupported({TargetOpcode::G_IMPLICIT_DEF, {DstTy}}))
         return false;
       DEBUG(dbgs() << ".. Combine EXT(IMPLICIT_DEF) " << MI;);
       Builder.setInstr(MI);
       Builder.buildInstr(TargetOpcode::G_IMPLICIT_DEF, DstReg);
       markInstAndDefDead(MI, *DefMI, DeadInsts);
       return true;
     }
     return false;
void markInstAndDefDead(MachineInstr &MI, MachineInstr &DefMI,
     if ((PrevMI == &DefMI ||
          DefMI.getOpcode() == TargetOpcode::G_MERGE_VALUES) &&
         MRI.hasOneUse(DefMI.getOperand(0).getReg()))
       DeadInsts.push_back(&DefMI);
   }
 
   /// Checks if the target legalizer info has specified anything about the
   /// instruction, or if unsupported.
-  bool isInstUnsupported(unsigned Opcode, const LLT &DstTy) const {
-    auto Action = LI.getAction({Opcode, 0, DstTy});
-    return Action.first == LegalizerInfo::LegalizeAction::Unsupported ||
-           Action.first == LegalizerInfo::LegalizeAction::NotFound;
+  bool isInstUnsupported(const LegalityQuery &Query) const {
+    auto Step = LI.getAction(Query);
+    return Step.Action == LegalizerInfo::LegalizeAction::Unsupported ||
+           Step.Action == LegalizerInfo::LegalizeAction::NotFound;
   }
 };
 
 } // namespace llvm

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

struct InstrAspect {
   InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
       : Opcode(Opcode), Idx(Idx), Type(Type) {}
 
   bool operator==(const InstrAspect &RHS) const {
     return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
   }
 };
 
+/// The LegalityQuery object bundles together all the information that's needed
+/// to decide whether a given operation is legal or not.
+/// 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;
+};
+
 class LegalizerInfo {
 public:
   enum LegalizeAction : std::uint8_t {
     /// The operation is expected to be selectable directly by the target, and
     /// no transformation is necessary.
     Legal,
 
     /// The operation should be synthesized from multiple instructions acting on
enum LegalizeAction : std::uint8_t {
     /// This operation is completely unsupported on the target. A programming
     /// error has occurred.
     Unsupported,
 
     /// Sentinel value for when no action was found in the specified table.
     NotFound,
   };
 
+  /// The result of a query. It either indicates a final answer of Legal or
+  /// Unsupported or describes an action that must be taken to make an operation
+  /// more legal.
+  struct LegalizeActionStep {
+    /// The action to take or the final answer.
+    LegalizeAction Action;
+    /// If describing an action, the type index to change. Otherwise zero.
+    unsigned TypeIdx;
+    /// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
+    LLT NewType;
+
+    LegalizeActionStep(LegalizeAction Action, unsigned TypeIdx,
+                       const LLT &NewType)
+        : Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}
+
+    bool operator==(const LegalizeActionStep &RHS) const {
+      return std::tie(Action, TypeIdx, NewType) ==
+          std::tie(RHS.Action, RHS.TypeIdx, RHS.NewType);
+    }
+  };
+
   LegalizerInfo();
   virtual ~LegalizerInfo() = default;
 
   /// Compute any ancillary tables needed to quickly decide how an operation
   /// should be handled. This must be called after all "set*Action"methods but
   /// before any query is made or incorrect results may be returned.
   void computeTables();
 
increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
                                             LegalizeAction IncreaseAction,
                                             LegalizeAction DecreaseAction);
   /// Helper function to implement many typical SizeChangeStrategy functions.
   static SizeAndActionsVec
   decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v,
                                               LegalizeAction DecreaseAction,
                                               LegalizeAction IncreaseAction);
 
-  /// Determine what action should be taken to legalize the given generic
-  /// instruction opcode, type-index and type. Requires computeTables to have
-  /// been called.
+  /// Determine what action should be taken to legalize the described
+  /// instruction. Requires computeTables to have been called.
   ///
-  /// \returns a pair consisting of the kind of legalization that should be
-  /// performed and the destination type.
-  std::pair<LegalizeAction, LLT> getAction(const InstrAspect &Aspect) const;
+  /// \returns a description of the next legalization step to perform.
+  LegalizeActionStep getAction(const LegalityQuery &Query) const;
 
   /// Determine what action should be taken to legalize the given generic
   /// instruction.
   ///
-  /// \returns a tuple consisting of the LegalizeAction that should be
-  /// performed, the type-index it should be performed on and the destination
-  /// type.
-  std::tuple<LegalizeAction, unsigned, LLT>
-  getAction(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
+  /// \returns a description of the next legalization step to perform.
+  LegalizeActionStep getAction(const MachineInstr &MI,
+                               const MachineRegisterInfo &MRI) const;
 
   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 
   virtual bool legalizeCustom(MachineInstr &MI,
                               MachineRegisterInfo &MRI,
                               MachineIRBuilder &MIRBuilder) const;
 
 private:
+  /// Determine what action should be taken to legalize the given generic
+  /// instruction opcode, type-index and type. Requires computeTables to have
+  /// been called.
+  ///
+  /// \returns a pair consisting of the kind of legalization that should be
+  /// performed and the destination type.
+  std::pair<LegalizeAction, LLT>
+  getAspectAction(const InstrAspect &Aspect) const;
+
   /// The SizeAndActionsVec is a representation mapping between all natural
   /// numbers and an Action. The natural number represents the bit size of
   /// the InstrAspect. For example, for a target with native support for 32-bit
   /// and 64-bit additions, you'd express that as:
   /// setScalarAction(G_ADD, 0,
   ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
   ///            {32, Legal},       // bit sizes [32, 33[
   ///            {33, WidenScalar}, // bit sizes [33, 64[

llvm/trunk/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

LegalizerHelper::LegalizerHelper(MachineFunction &MF)
     : MRI(MF.getRegInfo()), LI(*MF.getSubtarget().getLegalizerInfo()) {
   MIRBuilder.setMF(MF);
 }
 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
   DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
 
-  auto Action = LI.getAction(MI, MRI);
-  switch (std::get<0>(Action)) {
+  auto Step = LI.getAction(MI, MRI);
+  switch (Step.Action) {
   case LegalizerInfo::Legal:
     DEBUG(dbgs() << ".. Already legal\n");
     return AlreadyLegal;
   case LegalizerInfo::Libcall:
     DEBUG(dbgs() << ".. Convert to libcall\n");
     return libcall(MI);
   case LegalizerInfo::NarrowScalar:
     DEBUG(dbgs() << ".. Narrow scalar\n");
-    return narrowScalar(MI, std::get<1>(Action), std::get<2>(Action));
+    return narrowScalar(MI, Step.TypeIdx, Step.NewType);
   case LegalizerInfo::WidenScalar:
     DEBUG(dbgs() << ".. Widen scalar\n");
-    return widenScalar(MI, std::get<1>(Action), std::get<2>(Action));
+    return widenScalar(MI, Step.TypeIdx, Step.NewType);
   case LegalizerInfo::Lower:
     DEBUG(dbgs() << ".. Lower\n");
-    return lower(MI, std::get<1>(Action), std::get<2>(Action));
+    return lower(MI, Step.TypeIdx, Step.NewType);
   case LegalizerInfo::FewerElements:
     DEBUG(dbgs() << ".. Reduce number of elements\n");
-    return fewerElementsVector(MI, std::get<1>(Action), std::get<2>(Action));
+    return fewerElementsVector(MI, Step.TypeIdx, Step.NewType);
   case LegalizerInfo::Custom:
     DEBUG(dbgs() << ".. Custom legalization\n");
     return LI.legalizeCustom(MI, MRI, MIRBuilder) ? Legalized
                                                   : UnableToLegalize;
   default:
     DEBUG(dbgs() << ".. Unable to legalize\n");
     return UnableToLegalize;
   }
MIRBuilder.buildInstr(TargetOpcode::G_FSUB)
         .addUse(MI.getOperand(1).getReg());
     MI.eraseFromParent();
     return Legalized;
   }
   case TargetOpcode::G_FSUB: {
     // Lower (G_FSUB LHS, RHS) to (G_FADD LHS, (G_FNEG RHS)).
     // First, check if G_FNEG is marked as Lower. If so, we may
     // end up with an infinite loop as G_FSUB is used to legalize G_FNEG.
-    if (LI.getAction({G_FNEG, Ty}).first == LegalizerInfo::Lower)
+    if (LI.getAction({G_FNEG, {Ty}}).Action == LegalizerInfo::Lower)
       return UnableToLegalize;
     unsigned Res = MI.getOperand(0).getReg();
     unsigned LHS = MI.getOperand(1).getReg();
     unsigned RHS = MI.getOperand(2).getReg();
     unsigned Neg = MRI.createGenericVirtualRegister(Ty);
     MIRBuilder.buildInstr(TargetOpcode::G_FNEG).addDef(Neg).addUse(RHS);
     MIRBuilder.buildInstr(TargetOpcode::G_FADD)
         .addDef(Res)

llvm/trunk/lib/CodeGen/GlobalISel/LegalizerInfo.cpp

void LegalizerInfo::computeTables() {
   TablesInitialized = true;
 }
 
 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
 // probably going to need specialized lookup structures for various types before
 // we have any hope of doing well with something like <13 x i3>. Even the common
 // cases should do better than what we have now.
 std::pair<LegalizerInfo::LegalizeAction, LLT>
-LegalizerInfo::getAction(const InstrAspect &Aspect) const {
+LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
   assert(TablesInitialized && "backend forgot to call computeTables");
   // These *have* to be implemented for now, they're the fundamental basis of
   // how everything else is transformed.
   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
     return findScalarLegalAction(Aspect);
   assert(Aspect.Type.isVector());
   return findVectorLegalAction(Aspect);
 }
 
 /// Helper function to get LLT for the given type index.
 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
                               const MachineRegisterInfo &MRI, unsigned OpIdx,
                               unsigned TypeIdx) {
   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
   // G_UNMERGE_VALUES has variable number of operands, but there is only
   // one source type and one destination type as all destinations must be the
   // same type. So, get the last operand if TypeIdx == 1.
   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
   return MRI.getType(MI.getOperand(OpIdx).getReg());
 }
 
-std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
+LegalizerInfo::LegalizeActionStep
+LegalizerInfo::getAction(const LegalityQuery &Query) const {
+  for (unsigned i = 0; i < Query.Types.size(); ++i) {
+    auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
+    if (Action.first != Legal)
+      return {Action.first, i, Action.second};
+  }
+  return {Legal, 0, LLT{}};
+}
+
+LegalizerInfo::LegalizeActionStep
 LegalizerInfo::getAction(const MachineInstr &MI,
                          const MachineRegisterInfo &MRI) const {
+  SmallVector<LLT, 2> Types;
   SmallBitVector SeenTypes(8);
   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
   // FIXME: probably we'll need to cache the results here somehow?
   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
     if (!OpInfo[i].isGenericType())
       continue;
 
     // We must only record actions once for each TypeIdx; otherwise we'd
     // try to legalize operands multiple times down the line.
     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
     if (SeenTypes[TypeIdx])
       continue;
 
     SeenTypes.set(TypeIdx);
 
     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
-    auto Action = getAction({MI.getOpcode(), TypeIdx, Ty});
-    if (Action.first != Legal)
-      return std::make_tuple(Action.first, TypeIdx, Action.second);
+    Types.push_back(Ty);
   }
-  return std::make_tuple(Legal, 0, LLT{});
+  return getAction({MI.getOpcode(), Types});
 }
 
 bool LegalizerInfo::isLegal(const MachineInstr &MI,
                             const MachineRegisterInfo &MRI) const {
-  return std::get<0>(getAction(MI, MRI)) == Legal;
+  return getAction(MI, MRI).Action == Legal;
 }
 
 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
                                    MachineIRBuilder &MIRBuilder) const {
   return false;
 }
 
 LegalizerInfo::SizeAndActionsVec

llvm/trunk/unittests/CodeGen/GlobalISel/LegalizerInfoTest.cpp

for (unsigned Op : {G_ADD, G_SUB}) {
     L.setLegalizeScalarToDifferentSizeStrategy(
         Op, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest);
   }
 
   L.computeTables();
 
   for (unsigned opcode : {G_ADD, G_SUB}) {
     // Check we infer the correct types and actually do what we're told.
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(8)}),
-              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(16)}),
-              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(32)}),
-              std::make_pair(LegalizerInfo::Legal, LLT::scalar(32)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(64)}),
-              std::make_pair(LegalizerInfo::Legal, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(8)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(16)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(32)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::Legal, 0, LLT{}));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(64)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::Legal, 0, LLT{}));
 
     // Make sure the default for over-sized types applies.
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(128)}),
-              std::make_pair(LegalizerInfo::NarrowScalar, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(128)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::NarrowScalar, 0, LLT::scalar(64)));
     // Make sure we also handle unusual sizes
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(1)}),
-              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(31)}),
-              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(33)}),
-              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(64)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(63)}),
-              std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(64)));
-    ASSERT_EQ(L.getAction({opcode, LLT::scalar(65)}),
-              std::make_pair(LegalizerInfo::NarrowScalar, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(1)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(31)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(33)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(63)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(64)));
+    ASSERT_EQ(L.getAction({opcode, {LLT::scalar(65)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::NarrowScalar, 0, LLT::scalar(64)));
   }
 }
 
 TEST(LegalizerInfoTest, VectorRISC) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   // Typical RISCy set of operations based on ARM.
   L.setAction({G_ADD, LLT::vector(8, 8)}, LegalizerInfo::Legal);
   L.setAction({G_ADD, LLT::vector(16, 8)}, LegalizerInfo::Legal);
   L.setAction({G_ADD, LLT::vector(4, 16)}, LegalizerInfo::Legal);
   L.setAction({G_ADD, LLT::vector(8, 16)}, LegalizerInfo::Legal);
   L.setAction({G_ADD, LLT::vector(2, 32)}, LegalizerInfo::Legal);
   L.setAction({G_ADD, LLT::vector(4, 32)}, LegalizerInfo::Legal);
 
   L.setLegalizeVectorElementToDifferentSizeStrategy(
       G_ADD, 0, LegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
 
   L.setAction({G_ADD, 0, LLT::scalar(32)}, LegalizerInfo::Legal);
 
   L.computeTables();
 
   // Check we infer the correct types and actually do what we're told for some
   // simple cases.
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 8)}),
-            std::make_pair(LegalizerInfo::Legal, LLT::vector(8, 8)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 7)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::vector(8, 8)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(2, 8)}),
-            std::make_pair(LegalizerInfo::MoreElements, LLT::vector(8, 8)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(8, 32)}),
-            std::make_pair(LegalizerInfo::FewerElements, LLT::vector(4, 32)));
+  ASSERT_EQ(L.getAction({G_ADD, {LLT::vector(8, 8)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::Legal, 0, LLT{}));
+  ASSERT_EQ(L.getAction({G_ADD, {LLT::vector(8, 7)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::vector(8, 8)));
+  ASSERT_EQ(L.getAction({G_ADD, {LLT::vector(2, 8)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::MoreElements, 0, LLT::vector(8, 8)));
+  ASSERT_EQ(L.getAction({G_ADD, {LLT::vector(8, 32)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::FewerElements, 0, LLT::vector(4, 32)));
   // Check a few non-power-of-2 sizes:
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 3)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::vector(3, 8)));
-  ASSERT_EQ(L.getAction({G_ADD, LLT::vector(3, 8)}),
-            std::make_pair(LegalizerInfo::MoreElements, LLT::vector(8, 8)));
+  ASSERT_EQ(L.getAction({G_ADD, {LLT::vector(3, 3)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::vector(3, 8)));
+  ASSERT_EQ(L.getAction({G_ADD, {LLT::vector(3, 8)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::MoreElements, 0, LLT::vector(8, 8)));
 }
 
 TEST(LegalizerInfoTest, MultipleTypes) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   LLT p0 = LLT::pointer(0, 64);
   LLT s64 = LLT::scalar(64);
 
   // Typical RISCy set of operations based on AArch64.
   L.setAction({G_PTRTOINT, 0, s64}, LegalizerInfo::Legal);
   L.setAction({G_PTRTOINT, 1, p0}, LegalizerInfo::Legal);
 
   L.setLegalizeScalarToDifferentSizeStrategy(
       G_PTRTOINT, 0, LegalizerInfo::widenToLargerTypesAndNarrowToLargest);
 
   L.computeTables();
 
   // Check we infer the correct types and actually do what we're told.
-  ASSERT_EQ(L.getAction({G_PTRTOINT, 0, s64}),
-            std::make_pair(LegalizerInfo::Legal, s64));
-  ASSERT_EQ(L.getAction({G_PTRTOINT, 1, p0}),
-            std::make_pair(LegalizerInfo::Legal, p0));
+  ASSERT_EQ(L.getAction({G_PTRTOINT, {s64, p0}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::Legal, 0, LLT{}));
+
   // Make sure we also handle unusual sizes
-  ASSERT_EQ(L.getAction({G_PTRTOINT, 0, LLT::scalar(65)}),
-            std::make_pair(LegalizerInfo::NarrowScalar, s64));
-  ASSERT_EQ(L.getAction({G_PTRTOINT, 1, LLT::pointer(0, 32)}),
-            std::make_pair(LegalizerInfo::Unsupported, LLT::pointer(0, 32)));
+  ASSERT_EQ(
+      L.getAction({G_PTRTOINT, {LLT::scalar(65), s64}}),
+      LegalizerInfo::LegalizeActionStep(LegalizerInfo::NarrowScalar, 0, s64));
+  ASSERT_EQ(
+      L.getAction({G_PTRTOINT, {s64, LLT::pointer(0, 32)}}),
+      LegalizerInfo::LegalizeActionStep(LegalizerInfo::Unsupported, 1, LLT::pointer(0, 32)));
 }
 
 TEST(LegalizerInfoTest, MultipleSteps) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   LLT s32 = LLT::scalar(32);
   LLT s64 = LLT::scalar(64);
 
   L.setLegalizeScalarToDifferentSizeStrategy(
       G_UREM, 0, LegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
   L.setAction({G_UREM, 0, s32}, LegalizerInfo::Lower);
   L.setAction({G_UREM, 0, s64}, LegalizerInfo::Lower);
 
   L.computeTables();
 
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(16)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(32)}),
-            std::make_pair(LegalizerInfo::Lower, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(16)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(32)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::Lower, 0, LLT::scalar(32)));
 }
 
 TEST(LegalizerInfoTest, SizeChangeStrategy) {
   using namespace TargetOpcode;
   LegalizerInfo L;
   for (unsigned Size : {1, 8, 16, 32})
     L.setAction({G_UREM, 0, LLT::scalar(Size)}, LegalizerInfo::Legal);
 
   L.setLegalizeScalarToDifferentSizeStrategy(
       G_UREM, 0, LegalizerInfo::widenToLargerTypesUnsupportedOtherwise);
   L.computeTables();
 
   // Check we infer the correct types and actually do what we're told.
   for (unsigned Size : {1, 8, 16, 32}) {
-    ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(Size)}),
-              std::make_pair(LegalizerInfo::Legal, LLT::scalar(Size)));
+    ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(Size)}}),
+              LegalizerInfo::LegalizeActionStep(LegalizerInfo::Legal, 0, LLT{}));
   }
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(2)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(8)));
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(7)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(8)));
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(9)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(16)));
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(17)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(31)}),
-            std::make_pair(LegalizerInfo::WidenScalar, LLT::scalar(32)));
-  ASSERT_EQ(L.getAction({G_UREM, LLT::scalar(33)}),
-            std::make_pair(LegalizerInfo::Unsupported, LLT::scalar(33)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(2)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(8)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(7)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(8)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(9)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(16)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(17)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(31)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::WidenScalar, 0, LLT::scalar(32)));
+  ASSERT_EQ(L.getAction({G_UREM, {LLT::scalar(33)}}),
+            LegalizerInfo::LegalizeActionStep(LegalizerInfo::Unsupported, 0, LLT::scalar(33)));
 }
 }