[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

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

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

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

[dsanders]

include/llvm/CodeGen/GlobalISel/LegalizerInfo.h

56

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

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.

126–129

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

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

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 Action = LI.getAction(Query);
+    return std::get<0>(Action) == LegalizerInfo::LegalizeAction::Unsupported ||
+           std::get<0>(Action) == LegalizerInfo::LegalizeAction::NotFound;
   }
 };
 
 } // namespace llvm

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;
   }
 };
 
+struct LegalityQuery {
+  unsigned Opcode;
+  ArrayRef<LLT> Types;
+
+  LegalityQuery(unsigned Opcode, ArrayRef<LLT> Types)
+      : Opcode(Opcode), Types(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
     /// a narrower scalar base-type. For example a 64-bit add might be
     /// implemented in terms of 32-bit add-with-carry.
public:
 
   static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
     switch (Action) {
     case NarrowScalar:
     case WidenScalar:
     case FewerElements:
     case MoreElements:
     case Unsupported:
       return true;
     default:
       return false;
     }
   }
 
   typedef std::pair<uint16_t, LegalizeAction> SizeAndAction;
   typedef std::vector<SizeAndAction> SizeAndActionsVec;
   using SizeChangeStrategy =
       std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
 
   /// More friendly way to set an action for common types that have an LLT
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;
+  std::tuple<LegalizeAction, unsigned, LLT>
+  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;
 
   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[

lib/CodeGen/GlobalISel/LegalizerHelper.cpp

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 (std::get<0>(LI.getAction({G_FNEG, {Ty}})) == 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)

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::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 std::make_tuple(Action.first, i, Action.second);
+  }
+  return std::make_tuple(Legal, 0, LLT{});
+}
+
+std::tuple<LegalizerInfo::LegalizeAction, unsigned, LLT>
 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;
 }
 
 bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,