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

   1 //===- llvm/CodeGen/GlobalISel/LegalizerInfo.h ------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 /// Interface for Targets to specify which operations they can successfully
  11 /// select and how the others should be expanded most efficiently.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
  16 #define LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H
  17
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/None.h"
  20 #include "llvm/ADT/Optional.h"
  21 #include "llvm/ADT/STLExtras.h"
  22 #include "llvm/ADT/SmallBitVector.h"
  23 #include "llvm/ADT/SmallVector.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/TargetOpcodes.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/Support/LowLevelTypeImpl.h"
  28 #include <cassert>
  29 #include <cstdint>
  30 #include <tuple>
  31 #include <unordered_map>
  32 #include <utility>
  33
  34 namespace llvm {
  35
  36 extern cl::opt<bool> DisableGISelLegalityCheck;
  37
  38 class MachineInstr;
  39 class MachineIRBuilder;
  40 class MachineRegisterInfo;
  41 class MCInstrInfo;
  42 class GISelChangeObserver;
  43
  44 namespace LegalizeActions {
  45 enum LegalizeAction : std::uint8_t {
  46   /// The operation is expected to be selectable directly by the target, and
  47   /// no transformation is necessary.
  48   Legal,
  49
  50   /// The operation should be synthesized from multiple instructions acting on
  51   /// a narrower scalar base-type. For example a 64-bit add might be
  52   /// implemented in terms of 32-bit add-with-carry.
  53   NarrowScalar,
  54
  55   /// The operation should be implemented in terms of a wider scalar
  56   /// base-type. For example a <2 x s8> add could be implemented as a <2
  57   /// x s32> add (ignoring the high bits).
  58   WidenScalar,
  59
  60   /// The (vector) operation should be implemented by splitting it into
  61   /// sub-vectors where the operation is legal. For example a <8 x s64> add
  62   /// might be implemented as 4 separate <2 x s64> adds.
  63   FewerElements,
  64
  65   /// The (vector) operation should be implemented by widening the input
  66   /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
  67   /// rarely legal, but you might perform an <8 x i8> and then only look at
  68   /// the first two results.
  69   MoreElements,
  70
  71   /// The operation itself must be expressed in terms of simpler actions on
  72   /// this target. E.g. a SREM replaced by an SDIV and subtraction.
  73   Lower,
  74
  75   /// The operation should be implemented as a call to some kind of runtime
  76   /// support library. For example this usually happens on machines that don't
  77   /// support floating-point operations natively.
  78   Libcall,
  79
  80   /// The target wants to do something special with this combination of
  81   /// operand and type. A callback will be issued when it is needed.
  82   Custom,
  83
  84   /// This operation is completely unsupported on the target. A programming
  85   /// error has occurred.
  86   Unsupported,
  87
  88   /// Sentinel value for when no action was found in the specified table.
  89   NotFound,
  90
  91   /// Fall back onto the old rules.
  92   /// TODO: Remove this once we've migrated
  93   UseLegacyRules,
  94 };
  95 } // end namespace LegalizeActions
  96
  97 using LegalizeActions::LegalizeAction;
  98
  99 /// Legalization is decided based on an instruction's opcode, which type slot
 100 /// we're considering, and what the existing type is. These aspects are gathered
 101 /// together for convenience in the InstrAspect class.
 102 struct InstrAspect {
 103   unsigned Opcode;
 104   unsigned Idx = 0;
 105   LLT Type;
 106
 107   InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
 108   InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
 109       : Opcode(Opcode), Idx(Idx), Type(Type) {}
 110
 111   bool operator==(const InstrAspect &RHS) const {
 112     return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
 113   }
 114 };
 115
 116 /// The LegalityQuery object bundles together all the information that's needed
 117 /// to decide whether a given operation is legal or not.
 118 /// For efficiency, it doesn't make a copy of Types so care must be taken not
 119 /// to free it before using the query.
 120 struct LegalityQuery {
 121   unsigned Opcode;
 122   ArrayRef<LLT> Types;
 123
 124   struct MemDesc {
 125     uint64_t SizeInBits;
 126     AtomicOrdering Ordering;
 127   };
 128
 129   /// Operations which require memory can use this to place requirements on the
 130   /// memory type for each MMO.
 131   ArrayRef<MemDesc> MMODescrs;
 132
 133   constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types,
 134                           const ArrayRef<MemDesc> MMODescrs)
 135       : Opcode(Opcode), Types(Types), MMODescrs(MMODescrs) {}
 136   constexpr LegalityQuery(unsigned Opcode, const ArrayRef<LLT> Types)
 137       : LegalityQuery(Opcode, Types, {}) {}
 138
 139   raw_ostream &print(raw_ostream &OS) const;
 140 };
 141
 142 /// The result of a query. It either indicates a final answer of Legal or
 143 /// Unsupported or describes an action that must be taken to make an operation
 144 /// more legal.
 145 struct LegalizeActionStep {
 146   /// The action to take or the final answer.
 147   LegalizeAction Action;
 148   /// If describing an action, the type index to change. Otherwise zero.
 149   unsigned TypeIdx;
 150   /// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
 151   LLT NewType;
 152
 153   LegalizeActionStep(LegalizeAction Action, unsigned TypeIdx,
 154                      const LLT &NewType)
 155       : Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}
 156
 157   bool operator==(const LegalizeActionStep &RHS) const {
 158     return std::tie(Action, TypeIdx, NewType) ==
 159         std::tie(RHS.Action, RHS.TypeIdx, RHS.NewType);
 160   }
 161 };
 162
 163 using LegalityPredicate = std::function<bool (const LegalityQuery &)>;
 164 using LegalizeMutation =
 165     std::function<std::pair<unsigned, LLT>(const LegalityQuery &)>;
 166
 167 namespace LegalityPredicates {
 168 struct TypePairAndMemSize {
 169   LLT Type0;
 170   LLT Type1;
 171   uint64_t MemSize;
 172
 173   bool operator==(const TypePairAndMemSize &Other) const {
 174     return Type0 == Other.Type0 && Type1 == Other.Type1 &&
 175            MemSize == Other.MemSize;
 176   }
 177 };
 178
 179 /// True iff P0 and P1 are true.
 180 template<typename Predicate>
 181 Predicate all(Predicate P0, Predicate P1) {
 182   return [=](const LegalityQuery &Query) {
 183     return P0(Query) && P1(Query);
 184   };
 185 }
 186 /// True iff all given predicates are true.
 187 template<typename Predicate, typename... Args>
 188 Predicate all(Predicate P0, Predicate P1, Args... args) {
 189   return all(all(P0, P1), args...);
 190 }
 191 /// True iff the given type index is the specified types.
 192 LegalityPredicate typeIs(unsigned TypeIdx, LLT TypesInit);
 193 /// True iff the given type index is one of the specified types.
 194 LegalityPredicate typeInSet(unsigned TypeIdx,
 195                             std::initializer_list<LLT> TypesInit);
 196 /// True iff the given types for the given pair of type indexes is one of the
 197 /// specified type pairs.
 198 LegalityPredicate
 199 typePairInSet(unsigned TypeIdx0, unsigned TypeIdx1,
 200               std::initializer_list<std::pair<LLT, LLT>> TypesInit);
 201 /// True iff the given types for the given pair of type indexes is one of the
 202 /// specified type pairs.
 203 LegalityPredicate typePairAndMemSizeInSet(
 204     unsigned TypeIdx0, unsigned TypeIdx1, unsigned MMOIdx,
 205     std::initializer_list<TypePairAndMemSize> TypesAndMemSizeInit);
 206 /// True iff the specified type index is a scalar.
 207 LegalityPredicate isScalar(unsigned TypeIdx);
 208 /// True iff the specified type index is a scalar that's narrower than the given
 209 /// size.
 210 LegalityPredicate narrowerThan(unsigned TypeIdx, unsigned Size);
 211 /// True iff the specified type index is a scalar that's wider than the given
 212 /// size.
 213 LegalityPredicate widerThan(unsigned TypeIdx, unsigned Size);
 214 /// True iff the specified type index is a scalar whose size is not a power of
 215 /// 2.
 216 LegalityPredicate sizeNotPow2(unsigned TypeIdx);
 217 /// True iff the specified MMO index has a size that is not a power of 2
 218 LegalityPredicate memSizeInBytesNotPow2(unsigned MMOIdx);
 219 /// True iff the specified type index is a vector whose element count is not a
 220 /// power of 2.
 221 LegalityPredicate numElementsNotPow2(unsigned TypeIdx);
 222 /// True iff the specified MMO index has at an atomic ordering of at Ordering or
 223 /// stronger.
 224 LegalityPredicate atomicOrderingAtLeastOrStrongerThan(unsigned MMOIdx,
 225                                                       AtomicOrdering Ordering);
 226 } // end namespace LegalityPredicates
 227
 228 namespace LegalizeMutations {
 229 /// Select this specific type for the given type index.
 230 LegalizeMutation changeTo(unsigned TypeIdx, LLT Ty);
 231 /// Keep the same type as the given type index.
 232 LegalizeMutation changeTo(unsigned TypeIdx, unsigned FromTypeIdx);
 233 /// Widen the type for the given type index to the next power of 2.
 234 LegalizeMutation widenScalarToNextPow2(unsigned TypeIdx, unsigned Min = 0);
 235 /// Add more elements to the type for the given type index to the next power of
 236 /// 2.
 237 LegalizeMutation moreElementsToNextPow2(unsigned TypeIdx, unsigned Min = 0);
 238 } // end namespace LegalizeMutations
 239
 240 /// A single rule in a legalizer info ruleset.
 241 /// The specified action is chosen when the predicate is true. Where appropriate
 242 /// for the action (e.g. for WidenScalar) the new type is selected using the
 243 /// given mutator.
 244 class LegalizeRule {
 245   LegalityPredicate Predicate;
 246   LegalizeAction Action;
 247   LegalizeMutation Mutation;
 248
 249 public:
 250   LegalizeRule(LegalityPredicate Predicate, LegalizeAction Action,
 251                LegalizeMutation Mutation = nullptr)
 252       : Predicate(Predicate), Action(Action), Mutation(Mutation) {}
 253
 254   /// Test whether the LegalityQuery matches.
 255   bool match(const LegalityQuery &Query) const {
 256     return Predicate(Query);
 257   }
 258
 259   LegalizeAction getAction() const { return Action; }
 260
 261   /// Determine the change to make.
 262   std::pair<unsigned, LLT> determineMutation(const LegalityQuery &Query) const {
 263     if (Mutation)
 264       return Mutation(Query);
 265     return std::make_pair(0, LLT{});
 266   }
 267 };
 268
 269 class LegalizeRuleSet {
 270   /// When non-zero, the opcode we are an alias of
 271   unsigned AliasOf;
 272   /// If true, there is another opcode that aliases this one
 273   bool IsAliasedByAnother;
 274   SmallVector<LegalizeRule, 2> Rules;
 275
 276 #ifndef NDEBUG
 277   /// If bit I is set, this rule set contains a rule that may handle (predicate
 278   /// or perform an action upon (or both)) the type index I. The uncertainty
 279   /// comes from free-form rules executing user-provided lambda functions. We
 280   /// conservatively assume such rules do the right thing and cover all type
 281   /// indices. The bitset is intentionally 1 bit wider than it absolutely needs
 282   /// to be to distinguish such cases from the cases where all type indices are
 283   /// individually handled.
 284   SmallBitVector TypeIdxsCovered{MCOI::OPERAND_LAST_GENERIC -
 285                                  MCOI::OPERAND_FIRST_GENERIC + 2};
 286 #endif
 287
 288   unsigned typeIdx(unsigned TypeIdx) {
 289     assert(TypeIdx <=
 290                (MCOI::OPERAND_LAST_GENERIC - MCOI::OPERAND_FIRST_GENERIC) &&
 291            "Type Index is out of bounds");
 292 #ifndef NDEBUG
 293     TypeIdxsCovered.set(TypeIdx);
 294 #endif
 295     return TypeIdx;
 296   }
 297   void markAllTypeIdxsAsCovered() {
 298 #ifndef NDEBUG
 299     TypeIdxsCovered.set();
 300 #endif
 301   }
 302
 303   void add(const LegalizeRule &Rule) {
 304     assert(AliasOf == 0 &&
 305            "RuleSet is aliased, change the representative opcode instead");
 306     Rules.push_back(Rule);
 307   }
 308
 309   static bool always(const LegalityQuery &) { return true; }
 310
 311   /// Use the given action when the predicate is true.
 312   /// Action should not be an action that requires mutation.
 313   LegalizeRuleSet &actionIf(LegalizeAction Action,
 314                             LegalityPredicate Predicate) {
 315     add({Predicate, Action});
 316     return *this;
 317   }
 318   /// Use the given action when the predicate is true.
 319   /// Action should be an action that requires mutation.
 320   LegalizeRuleSet &actionIf(LegalizeAction Action, LegalityPredicate Predicate,
 321                             LegalizeMutation Mutation) {
 322     add({Predicate, Action, Mutation});
 323     return *this;
 324   }
 325   /// Use the given action when type index 0 is any type in the given list.
 326   /// Action should not be an action that requires mutation.
 327   LegalizeRuleSet &actionFor(LegalizeAction Action,
 328                              std::initializer_list<LLT> Types) {
 329     using namespace LegalityPredicates;
 330     return actionIf(Action, typeInSet(typeIdx(0), Types));
 331   }
 332   /// Use the given action when type index 0 is any type in the given list.
 333   /// Action should be an action that requires mutation.
 334   LegalizeRuleSet &actionFor(LegalizeAction Action,
 335                              std::initializer_list<LLT> Types,
 336                              LegalizeMutation Mutation) {
 337     using namespace LegalityPredicates;
 338     return actionIf(Action, typeInSet(typeIdx(0), Types), Mutation);
 339   }
 340   /// Use the given action when type indexes 0 and 1 is any type pair in the
 341   /// given list.
 342   /// Action should not be an action that requires mutation.
 343   LegalizeRuleSet &actionFor(LegalizeAction Action,
 344                              std::initializer_list<std::pair<LLT, LLT>> Types) {
 345     using namespace LegalityPredicates;
 346     return actionIf(Action, typePairInSet(typeIdx(0), typeIdx(1), Types));
 347   }
 348   /// Use the given action when type indexes 0 and 1 is any type pair in the
 349   /// given list.
 350   /// Action should be an action that requires mutation.
 351   LegalizeRuleSet &actionFor(LegalizeAction Action,
 352                              std::initializer_list<std::pair<LLT, LLT>> Types,
 353                              LegalizeMutation Mutation) {
 354     using namespace LegalityPredicates;
 355     return actionIf(Action, typePairInSet(typeIdx(0), typeIdx(1), Types),
 356                     Mutation);
 357   }
 358   /// Use the given action when type indexes 0 and 1 are both in the given list.
 359   /// That is, the type pair is in the cartesian product of the list.
 360   /// Action should not be an action that requires mutation.
 361   LegalizeRuleSet &actionForCartesianProduct(LegalizeAction Action,
 362                                              std::initializer_list<LLT> Types) {
 363     using namespace LegalityPredicates;
 364     return actionIf(Action, all(typeInSet(typeIdx(0), Types),
 365                                 typeInSet(typeIdx(1), Types)));
 366   }
 367   /// Use the given action when type indexes 0 and 1 are both in their
 368   /// respective lists.
 369   /// That is, the type pair is in the cartesian product of the lists
 370   /// Action should not be an action that requires mutation.
 371   LegalizeRuleSet &
 372   actionForCartesianProduct(LegalizeAction Action,
 373                             std::initializer_list<LLT> Types0,
 374                             std::initializer_list<LLT> Types1) {
 375     using namespace LegalityPredicates;
 376     return actionIf(Action, all(typeInSet(typeIdx(0), Types0),
 377                                 typeInSet(typeIdx(1), Types1)));
 378   }
 379   /// Use the given action when type indexes 0, 1, and 2 are all in their
 380   /// respective lists.
 381   /// That is, the type triple is in the cartesian product of the lists
 382   /// Action should not be an action that requires mutation.
 383   LegalizeRuleSet &actionForCartesianProduct(
 384       LegalizeAction Action, std::initializer_list<LLT> Types0,
 385       std::initializer_list<LLT> Types1, std::initializer_list<LLT> Types2) {
 386     using namespace LegalityPredicates;
 387     return actionIf(Action, all(typeInSet(typeIdx(0), Types0),
 388                                 all(typeInSet(typeIdx(1), Types1),
 389                                     typeInSet(typeIdx(2), Types2))));
 390   }
 391
 392 public:
 393   LegalizeRuleSet() : AliasOf(0), IsAliasedByAnother(false), Rules() {}
 394
 395   bool isAliasedByAnother() { return IsAliasedByAnother; }
 396   void setIsAliasedByAnother() { IsAliasedByAnother = true; }
 397   void aliasTo(unsigned Opcode) {
 398     assert((AliasOf == 0 || AliasOf == Opcode) &&
 399            "Opcode is already aliased to another opcode");
 400     assert(Rules.empty() && "Aliasing will discard rules");
 401     AliasOf = Opcode;
 402   }
 403   unsigned getAlias() const { return AliasOf; }
 404
 405   /// The instruction is legal if predicate is true.
 406   LegalizeRuleSet &legalIf(LegalityPredicate Predicate) {
 407     // We have no choice but conservatively assume that the free-form
 408     // user-provided Predicate properly handles all type indices:
 409     markAllTypeIdxsAsCovered();
 410     return actionIf(LegalizeAction::Legal, Predicate);
 411   }
 412   /// The instruction is legal when type index 0 is any type in the given list.
 413   LegalizeRuleSet &legalFor(std::initializer_list<LLT> Types) {
 414     return actionFor(LegalizeAction::Legal, Types);
 415   }
 416   /// The instruction is legal when type indexes 0 and 1 is any type pair in the
 417   /// given list.
 418   LegalizeRuleSet &legalFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
 419     return actionFor(LegalizeAction::Legal, Types);
 420   }
 421   /// The instruction is legal when type indexes 0 and 1 along with the memory
 422   /// size is any type and size tuple in the given list.
 423   LegalizeRuleSet &legalForTypesWithMemSize(
 424       std::initializer_list<LegalityPredicates::TypePairAndMemSize>
 425           TypesAndMemSize) {
 426     return actionIf(LegalizeAction::Legal,
 427                     LegalityPredicates::typePairAndMemSizeInSet(
 428                         typeIdx(0), typeIdx(1), /*MMOIdx*/ 0, TypesAndMemSize));
 429   }
 430   /// The instruction is legal when type indexes 0 and 1 are both in the given
 431   /// list. That is, the type pair is in the cartesian product of the list.
 432   LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types) {
 433     return actionForCartesianProduct(LegalizeAction::Legal, Types);
 434   }
 435   /// The instruction is legal when type indexes 0 and 1 are both their
 436   /// respective lists.
 437   LegalizeRuleSet &legalForCartesianProduct(std::initializer_list<LLT> Types0,
 438                                             std::initializer_list<LLT> Types1) {
 439     return actionForCartesianProduct(LegalizeAction::Legal, Types0, Types1);
 440   }
 441
 442   /// The instruction is lowered.
 443   LegalizeRuleSet &lower() {
 444     using namespace LegalizeMutations;
 445     // We have no choice but conservatively assume that predicate-less lowering
 446     // properly handles all type indices by design:
 447     markAllTypeIdxsAsCovered();
 448     return actionIf(LegalizeAction::Lower, always);
 449   }
 450   /// The instruction is lowered if predicate is true. Keep type index 0 as the
 451   /// same type.
 452   LegalizeRuleSet &lowerIf(LegalityPredicate Predicate) {
 453     using namespace LegalizeMutations;
 454     // We have no choice but conservatively assume that lowering with a
 455     // free-form user provided Predicate properly handles all type indices:
 456     markAllTypeIdxsAsCovered();
 457     return actionIf(LegalizeAction::Lower, Predicate);
 458   }
 459   /// The instruction is lowered if predicate is true.
 460   LegalizeRuleSet &lowerIf(LegalityPredicate Predicate,
 461                            LegalizeMutation Mutation) {
 462     // We have no choice but conservatively assume that lowering with a
 463     // free-form user provided Predicate properly handles all type indices:
 464     markAllTypeIdxsAsCovered();
 465     return actionIf(LegalizeAction::Lower, Predicate, Mutation);
 466   }
 467   /// The instruction is lowered when type index 0 is any type in the given
 468   /// list. Keep type index 0 as the same type.
 469   LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types) {
 470     return actionFor(LegalizeAction::Lower, Types,
 471                      LegalizeMutations::changeTo(0, 0));
 472   }
 473   /// The instruction is lowered when type index 0 is any type in the given
 474   /// list.
 475   LegalizeRuleSet &lowerFor(std::initializer_list<LLT> Types,
 476                             LegalizeMutation Mutation) {
 477     return actionFor(LegalizeAction::Lower, Types, Mutation);
 478   }
 479   /// The instruction is lowered when type indexes 0 and 1 is any type pair in
 480   /// the given list. Keep type index 0 as the same type.
 481   LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
 482     return actionFor(LegalizeAction::Lower, Types,
 483                      LegalizeMutations::changeTo(0, 0));
 484   }
 485   /// The instruction is lowered when type indexes 0 and 1 is any type pair in
 486   /// the given list.
 487   LegalizeRuleSet &lowerFor(std::initializer_list<std::pair<LLT, LLT>> Types,
 488                             LegalizeMutation Mutation) {
 489     return actionFor(LegalizeAction::Lower, Types, Mutation);
 490   }
 491   /// The instruction is lowered when type indexes 0 and 1 are both in their
 492   /// respective lists.
 493   LegalizeRuleSet &lowerForCartesianProduct(std::initializer_list<LLT> Types0,
 494                                             std::initializer_list<LLT> Types1) {
 495     using namespace LegalityPredicates;
 496     return actionForCartesianProduct(LegalizeAction::Lower, Types0, Types1);
 497   }
 498   /// The instruction is lowered when when type indexes 0, 1, and 2 are all in
 499   /// their respective lists.
 500   LegalizeRuleSet &lowerForCartesianProduct(std::initializer_list<LLT> Types0,
 501                                             std::initializer_list<LLT> Types1,
 502                                             std::initializer_list<LLT> Types2) {
 503     using namespace LegalityPredicates;
 504     return actionForCartesianProduct(LegalizeAction::Lower, Types0, Types1,
 505                                      Types2);
 506   }
 507
 508   /// Like legalIf, but for the Libcall action.
 509   LegalizeRuleSet &libcallIf(LegalityPredicate Predicate) {
 510     // We have no choice but conservatively assume that a libcall with a
 511     // free-form user provided Predicate properly handles all type indices:
 512     markAllTypeIdxsAsCovered();
 513     return actionIf(LegalizeAction::Libcall, Predicate);
 514   }
 515   LegalizeRuleSet &libcallFor(std::initializer_list<LLT> Types) {
 516     return actionFor(LegalizeAction::Libcall, Types);
 517   }
 518   LegalizeRuleSet &
 519   libcallFor(std::initializer_list<std::pair<LLT, LLT>> Types) {
 520     return actionFor(LegalizeAction::Libcall, Types);
 521   }
 522   LegalizeRuleSet &
 523   libcallForCartesianProduct(std::initializer_list<LLT> Types) {
 524     return actionForCartesianProduct(LegalizeAction::Libcall, Types);
 525   }
 526   LegalizeRuleSet &
 527   libcallForCartesianProduct(std::initializer_list<LLT> Types0,
 528                              std::initializer_list<LLT> Types1) {
 529     return actionForCartesianProduct(LegalizeAction::Libcall, Types0, Types1);
 530   }
 531
 532   /// Widen the scalar to the one selected by the mutation if the predicate is
 533   /// true.
 534   LegalizeRuleSet &widenScalarIf(LegalityPredicate Predicate,
 535                                  LegalizeMutation Mutation) {
 536     // We have no choice but conservatively assume that an action with a
 537     // free-form user provided Predicate properly handles all type indices:
 538     markAllTypeIdxsAsCovered();
 539     return actionIf(LegalizeAction::WidenScalar, Predicate, Mutation);
 540   }
 541   /// Narrow the scalar to the one selected by the mutation if the predicate is
 542   /// true.
 543   LegalizeRuleSet &narrowScalarIf(LegalityPredicate Predicate,
 544                                   LegalizeMutation Mutation) {
 545     // We have no choice but conservatively assume that an action with a
 546     // free-form user provided Predicate properly handles all type indices:
 547     markAllTypeIdxsAsCovered();
 548     return actionIf(LegalizeAction::NarrowScalar, Predicate, Mutation);
 549   }
 550
 551   /// Add more elements to reach the type selected by the mutation if the
 552   /// predicate is true.
 553   LegalizeRuleSet &moreElementsIf(LegalityPredicate Predicate,
 554                                   LegalizeMutation Mutation) {
 555     // We have no choice but conservatively assume that an action with a
 556     // free-form user provided Predicate properly handles all type indices:
 557     markAllTypeIdxsAsCovered();
 558     return actionIf(LegalizeAction::MoreElements, Predicate, Mutation);
 559   }
 560   /// Remove elements to reach the type selected by the mutation if the
 561   /// predicate is true.
 562   LegalizeRuleSet &fewerElementsIf(LegalityPredicate Predicate,
 563                                    LegalizeMutation Mutation) {
 564     // We have no choice but conservatively assume that an action with a
 565     // free-form user provided Predicate properly handles all type indices:
 566     markAllTypeIdxsAsCovered();
 567     return actionIf(LegalizeAction::FewerElements, Predicate, Mutation);
 568   }
 569
 570   /// The instruction is unsupported.
 571   LegalizeRuleSet &unsupported() {
 572     return actionIf(LegalizeAction::Unsupported, always);
 573   }
 574   LegalizeRuleSet &unsupportedIf(LegalityPredicate Predicate) {
 575     return actionIf(LegalizeAction::Unsupported, Predicate);
 576   }
 577   LegalizeRuleSet &unsupportedIfMemSizeNotPow2() {
 578     return actionIf(LegalizeAction::Unsupported,
 579                     LegalityPredicates::memSizeInBytesNotPow2(0));
 580   }
 581
 582   LegalizeRuleSet &customIf(LegalityPredicate Predicate) {
 583     // We have no choice but conservatively assume that a custom action with a
 584     // free-form user provided Predicate properly handles all type indices:
 585     markAllTypeIdxsAsCovered();
 586     return actionIf(LegalizeAction::Custom, Predicate);
 587   }
 588   LegalizeRuleSet &customFor(std::initializer_list<LLT> Types) {
 589     return actionFor(LegalizeAction::Custom, Types);
 590   }
 591   LegalizeRuleSet &customForCartesianProduct(std::initializer_list<LLT> Types) {
 592     return actionForCartesianProduct(LegalizeAction::Custom, Types);
 593   }
 594   LegalizeRuleSet &
 595   customForCartesianProduct(std::initializer_list<LLT> Types0,
 596                             std::initializer_list<LLT> Types1) {
 597     return actionForCartesianProduct(LegalizeAction::Custom, Types0, Types1);
 598   }
 599
 600   /// Widen the scalar to the next power of two that is at least MinSize.
 601   /// No effect if the type is not a scalar or is a power of two.
 602   LegalizeRuleSet &widenScalarToNextPow2(unsigned TypeIdx,
 603                                          unsigned MinSize = 0) {
 604     using namespace LegalityPredicates;
 605     return actionIf(LegalizeAction::WidenScalar, sizeNotPow2(typeIdx(TypeIdx)),
 606                     LegalizeMutations::widenScalarToNextPow2(TypeIdx, MinSize));
 607   }
 608
 609   LegalizeRuleSet &narrowScalar(unsigned TypeIdx, LegalizeMutation Mutation) {
 610     using namespace LegalityPredicates;
 611     return actionIf(LegalizeAction::NarrowScalar, isScalar(typeIdx(TypeIdx)),
 612                     Mutation);
 613   }
 614
 615   /// Ensure the scalar is at least as wide as Ty.
 616   LegalizeRuleSet &minScalar(unsigned TypeIdx, const LLT &Ty) {
 617     using namespace LegalityPredicates;
 618     using namespace LegalizeMutations;
 619     return actionIf(LegalizeAction::WidenScalar,
 620                     narrowerThan(TypeIdx, Ty.getSizeInBits()),
 621                     changeTo(typeIdx(TypeIdx), Ty));
 622   }
 623
 624   /// Ensure the scalar is at most as wide as Ty.
 625   LegalizeRuleSet &maxScalar(unsigned TypeIdx, const LLT &Ty) {
 626     using namespace LegalityPredicates;
 627     using namespace LegalizeMutations;
 628     return actionIf(LegalizeAction::NarrowScalar,
 629                     widerThan(TypeIdx, Ty.getSizeInBits()),
 630                     changeTo(typeIdx(TypeIdx), Ty));
 631   }
 632
 633   /// Conditionally limit the maximum size of the scalar.
 634   /// For example, when the maximum size of one type depends on the size of
 635   /// another such as extracting N bits from an M bit container.
 636   LegalizeRuleSet &maxScalarIf(LegalityPredicate Predicate, unsigned TypeIdx,
 637                                const LLT &Ty) {
 638     using namespace LegalityPredicates;
 639     using namespace LegalizeMutations;
 640     return actionIf(LegalizeAction::NarrowScalar,
 641                     [=](const LegalityQuery &Query) {
 642                       return widerThan(TypeIdx, Ty.getSizeInBits()) &&
 643                              Predicate(Query);
 644                     },
 645                     changeTo(typeIdx(TypeIdx), Ty));
 646   }
 647
 648   /// Limit the range of scalar sizes to MinTy and MaxTy.
 649   LegalizeRuleSet &clampScalar(unsigned TypeIdx, const LLT &MinTy,
 650                                const LLT &MaxTy) {
 651     assert(MinTy.isScalar() && MaxTy.isScalar() && "Expected scalar types");
 652     return minScalar(TypeIdx, MinTy).maxScalar(TypeIdx, MaxTy);
 653   }
 654
 655   /// Widen the scalar to match the size of another.
 656   LegalizeRuleSet &minScalarSameAs(unsigned TypeIdx, unsigned LargeTypeIdx) {
 657     typeIdx(TypeIdx);
 658     return widenScalarIf(
 659         [=](const LegalityQuery &Query) {
 660           return Query.Types[LargeTypeIdx].getScalarSizeInBits() >
 661                  Query.Types[TypeIdx].getSizeInBits();
 662         },
 663         [=](const LegalityQuery &Query) {
 664           return std::make_pair(TypeIdx,
 665                                 Query.Types[LargeTypeIdx].getElementType());
 666         });
 667   }
 668
 669   /// Add more elements to the vector to reach the next power of two.
 670   /// No effect if the type is not a vector or the element count is a power of
 671   /// two.
 672   LegalizeRuleSet &moreElementsToNextPow2(unsigned TypeIdx) {
 673     using namespace LegalityPredicates;
 674     return actionIf(LegalizeAction::MoreElements,
 675                     numElementsNotPow2(typeIdx(TypeIdx)),
 676                     LegalizeMutations::moreElementsToNextPow2(TypeIdx));
 677   }
 678
 679   /// Limit the number of elements in EltTy vectors to at least MinElements.
 680   LegalizeRuleSet &clampMinNumElements(unsigned TypeIdx, const LLT &EltTy,
 681                                        unsigned MinElements) {
 682     // Mark the type index as covered:
 683     typeIdx(TypeIdx);
 684     return actionIf(
 685         LegalizeAction::MoreElements,
 686         [=](const LegalityQuery &Query) {
 687           LLT VecTy = Query.Types[TypeIdx];
 688           return VecTy.isVector() && VecTy.getElementType() == EltTy &&
 689                  VecTy.getNumElements() < MinElements;
 690         },
 691         [=](const LegalityQuery &Query) {
 692           LLT VecTy = Query.Types[TypeIdx];
 693           return std::make_pair(
 694               TypeIdx, LLT::vector(MinElements, VecTy.getScalarSizeInBits()));
 695         });
 696   }
 697   /// Limit the number of elements in EltTy vectors to at most MaxElements.
 698   LegalizeRuleSet &clampMaxNumElements(unsigned TypeIdx, const LLT &EltTy,
 699                                        unsigned MaxElements) {
 700     // Mark the type index as covered:
 701     typeIdx(TypeIdx);
 702     return actionIf(
 703         LegalizeAction::FewerElements,
 704         [=](const LegalityQuery &Query) {
 705           LLT VecTy = Query.Types[TypeIdx];
 706           return VecTy.isVector() && VecTy.getElementType() == EltTy &&
 707                  VecTy.getNumElements() > MaxElements;
 708         },
 709         [=](const LegalityQuery &Query) {
 710           LLT VecTy = Query.Types[TypeIdx];
 711           if (MaxElements == 1)
 712             return std::make_pair(TypeIdx, VecTy.getElementType());
 713           return std::make_pair(
 714               TypeIdx, LLT::vector(MaxElements, VecTy.getScalarSizeInBits()));
 715         });
 716   }
 717   /// Limit the number of elements for the given vectors to at least MinTy's
 718   /// number of elements and at most MaxTy's number of elements.
 719   ///
 720   /// No effect if the type is not a vector or does not have the same element
 721   /// type as the constraints.
 722   /// The element type of MinTy and MaxTy must match.
 723   LegalizeRuleSet &clampNumElements(unsigned TypeIdx, const LLT &MinTy,
 724                                     const LLT &MaxTy) {
 725     assert(MinTy.getElementType() == MaxTy.getElementType() &&
 726            "Expected element types to agree");
 727
 728     const LLT &EltTy = MinTy.getElementType();
 729     return clampMinNumElements(TypeIdx, EltTy, MinTy.getNumElements())
 730         .clampMaxNumElements(TypeIdx, EltTy, MaxTy.getNumElements());
 731   }
 732
 733   /// Fallback on the previous implementation. This should only be used while
 734   /// porting a rule.
 735   LegalizeRuleSet &fallback() {
 736     add({always, LegalizeAction::UseLegacyRules});
 737     return *this;
 738   }
 739
 740   /// Check if there is no type index which is obviously not handled by the
 741   /// LegalizeRuleSet in any way at all.
 742   /// \pre Type indices of the opcode form a dense [0, \p NumTypeIdxs) set.
 743   bool verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const;
 744
 745   /// Apply the ruleset to the given LegalityQuery.
 746   LegalizeActionStep apply(const LegalityQuery &Query) const;
 747 };
 748
 749 class LegalizerInfo {
 750 public:
 751   LegalizerInfo();
 752   virtual ~LegalizerInfo() = default;
 753
 754   unsigned getOpcodeIdxForOpcode(unsigned Opcode) const;
 755   unsigned getActionDefinitionsIdx(unsigned Opcode) const;
 756
 757   /// Compute any ancillary tables needed to quickly decide how an operation
 758   /// should be handled. This must be called after all "set*Action"methods but
 759   /// before any query is made or incorrect results may be returned.
 760   void computeTables();
 761
 762   /// Perform simple self-diagnostic and assert if there is anything obviously
 763   /// wrong with the actions set up.
 764   void verify(const MCInstrInfo &MII) const;
 765
 766   static bool needsLegalizingToDifferentSize(const LegalizeAction Action) {
 767     using namespace LegalizeActions;
 768     switch (Action) {
 769     case NarrowScalar:
 770     case WidenScalar:
 771     case FewerElements:
 772     case MoreElements:
 773     case Unsupported:
 774       return true;
 775     default:
 776       return false;
 777     }
 778   }
 779
 780   using SizeAndAction = std::pair<uint16_t, LegalizeAction>;
 781   using SizeAndActionsVec = std::vector<SizeAndAction>;
 782   using SizeChangeStrategy =
 783       std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
 784
 785   /// More friendly way to set an action for common types that have an LLT
 786   /// representation.
 787   /// The LegalizeAction must be one for which NeedsLegalizingToDifferentSize
 788   /// returns false.
 789   void setAction(const InstrAspect &Aspect, LegalizeAction Action) {
 790     assert(!needsLegalizingToDifferentSize(Action));
 791     TablesInitialized = false;
 792     const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
 793     if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
 794       SpecifiedActions[OpcodeIdx].resize(Aspect.Idx + 1);
 795     SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
 796   }
 797
 798   /// The setAction calls record the non-size-changing legalization actions
 799   /// to take on specificly-sized types. The SizeChangeStrategy defines what
 800   /// to do when the size of the type needs to be changed to reach a legally
 801   /// sized type (i.e., one that was defined through a setAction call).
 802   /// e.g.
 803   /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
 804   /// setLegalizeScalarToDifferentSizeStrategy(
 805   ///   G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
 806   /// will end up defining getAction({G_ADD, 0, T}) to return the following
 807   /// actions for different scalar types T:
 808   ///  LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
 809   ///  LLT::scalar(32):                 {Legal, 0, LLT::scalar(32)}
 810   ///  LLT::scalar(33)..:               {NarrowScalar, 0, LLT::scalar(32)}
 811   ///
 812   /// If no SizeChangeAction gets defined, through this function,
 813   /// the default is unsupportedForDifferentSizes.
 814   void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
 815                                                 const unsigned TypeIdx,
 816                                                 SizeChangeStrategy S) {
 817     const unsigned OpcodeIdx = Opcode - FirstOp;
 818     if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
 819       ScalarSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
 820     ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
 821   }
 822
 823   /// See also setLegalizeScalarToDifferentSizeStrategy.
 824   /// This function allows to set the SizeChangeStrategy for vector elements.
 825   void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
 826                                                        const unsigned TypeIdx,
 827                                                        SizeChangeStrategy S) {
 828     const unsigned OpcodeIdx = Opcode - FirstOp;
 829     if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
 830       VectorElementSizeChangeStrategies[OpcodeIdx].resize(TypeIdx + 1);
 831     VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
 832   }
 833
 834   /// A SizeChangeStrategy for the common case where legalization for a
 835   /// particular operation consists of only supporting a specific set of type
 836   /// sizes. E.g.
 837   ///   setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
 838   ///   setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
 839   ///   setLegalizeScalarToDifferentSizeStrategy(
 840   ///     G_DIV, 0, unsupportedForDifferentSizes);
 841   /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
 842   /// and Unsupported for all other scalar types T.
 843   static SizeAndActionsVec
 844   unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
 845     using namespace LegalizeActions;
 846     return increaseToLargerTypesAndDecreaseToLargest(v, Unsupported,
 847                                                      Unsupported);
 848   }
 849
 850   /// A SizeChangeStrategy for the common case where legalization for a
 851   /// particular operation consists of widening the type to a large legal type,
 852   /// unless there is no such type and then instead it should be narrowed to the
 853   /// largest legal type.
 854   static SizeAndActionsVec
 855   widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
 856     using namespace LegalizeActions;
 857     assert(v.size() > 0 &&
 858            "At least one size that can be legalized towards is needed"
 859            " for this SizeChangeStrategy");
 860     return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
 861                                                      NarrowScalar);
 862   }
 863
 864   static SizeAndActionsVec
 865   widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
 866     using namespace LegalizeActions;
 867     return increaseToLargerTypesAndDecreaseToLargest(v, WidenScalar,
 868                                                      Unsupported);
 869   }
 870
 871   static SizeAndActionsVec
 872   narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
 873     using namespace LegalizeActions;
 874     return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
 875                                                        Unsupported);
 876   }
 877
 878   static SizeAndActionsVec
 879   narrowToSmallerAndWidenToSmallest(const SizeAndActionsVec &v) {
 880     using namespace LegalizeActions;
 881     assert(v.size() > 0 &&
 882            "At least one size that can be legalized towards is needed"
 883            " for this SizeChangeStrategy");
 884     return decreaseToSmallerTypesAndIncreaseToSmallest(v, NarrowScalar,
 885                                                        WidenScalar);
 886   }
 887
 888   /// A SizeChangeStrategy for the common case where legalization for a
 889   /// particular vector operation consists of having more elements in the
 890   /// vector, to a type that is legal. Unless there is no such type and then
 891   /// instead it should be legalized towards the widest vector that's still
 892   /// legal. E.g.
 893   ///   setAction({G_ADD, LLT::vector(8, 8)}, Legal);
 894   ///   setAction({G_ADD, LLT::vector(16, 8)}, Legal);
 895   ///   setAction({G_ADD, LLT::vector(2, 32)}, Legal);
 896   ///   setAction({G_ADD, LLT::vector(4, 32)}, Legal);
 897   ///   setLegalizeVectorElementToDifferentSizeStrategy(
 898   ///     G_ADD, 0, moreToWiderTypesAndLessToWidest);
 899   /// will result in the following getAction results:
 900   ///   * getAction({G_ADD, LLT::vector(8,8)}) returns
 901   ///       (Legal, vector(8,8)).
 902   ///   * getAction({G_ADD, LLT::vector(9,8)}) returns
 903   ///       (MoreElements, vector(16,8)).
 904   ///   * getAction({G_ADD, LLT::vector(8,32)}) returns
 905   ///       (FewerElements, vector(4,32)).
 906   static SizeAndActionsVec
 907   moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
 908     using namespace LegalizeActions;
 909     return increaseToLargerTypesAndDecreaseToLargest(v, MoreElements,
 910                                                      FewerElements);
 911   }
 912
 913   /// Helper function to implement many typical SizeChangeStrategy functions.
 914   static SizeAndActionsVec
 915   increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v,
 916                                             LegalizeAction IncreaseAction,
 917                                             LegalizeAction DecreaseAction);
 918   /// Helper function to implement many typical SizeChangeStrategy functions.
 919   static SizeAndActionsVec
 920   decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v,
 921                                               LegalizeAction DecreaseAction,
 922                                               LegalizeAction IncreaseAction);
 923
 924   /// Get the action definitions for the given opcode. Use this to run a
 925   /// LegalityQuery through the definitions.
 926   const LegalizeRuleSet &getActionDefinitions(unsigned Opcode) const;
 927
 928   /// Get the action definition builder for the given opcode. Use this to define
 929   /// the action definitions.
 930   ///
 931   /// It is an error to request an opcode that has already been requested by the
 932   /// multiple-opcode variant.
 933   LegalizeRuleSet &getActionDefinitionsBuilder(unsigned Opcode);
 934
 935   /// Get the action definition builder for the given set of opcodes. Use this
 936   /// to define the action definitions for multiple opcodes at once. The first
 937   /// opcode given will be considered the representative opcode and will hold
 938   /// the definitions whereas the other opcodes will be configured to refer to
 939   /// the representative opcode. This lowers memory requirements and very
 940   /// slightly improves performance.
 941   ///
 942   /// It would be very easy to introduce unexpected side-effects as a result of
 943   /// this aliasing if it were permitted to request different but intersecting
 944   /// sets of opcodes but that is difficult to keep track of. It is therefore an
 945   /// error to request the same opcode twice using this API, to request an
 946   /// opcode that already has definitions, or to use the single-opcode API on an
 947   /// opcode that has already been requested by this API.
 948   LegalizeRuleSet &
 949   getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes);
 950   void aliasActionDefinitions(unsigned OpcodeTo, unsigned OpcodeFrom);
 951
 952   /// Determine what action should be taken to legalize the described
 953   /// instruction. Requires computeTables to have been called.
 954   ///
 955   /// \returns a description of the next legalization step to perform.
 956   LegalizeActionStep getAction(const LegalityQuery &Query) const;
 957
 958   /// Determine what action should be taken to legalize the given generic
 959   /// instruction.
 960   ///
 961   /// \returns a description of the next legalization step to perform.
 962   LegalizeActionStep getAction(const MachineInstr &MI,
 963                                const MachineRegisterInfo &MRI) const;
 964
 965   bool isLegal(const MachineInstr &MI, const MachineRegisterInfo &MRI) const;
 966
 967   virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
 968                               MachineIRBuilder &MIRBuilder,
 969                               GISelChangeObserver &Observer) const;
 970
 971 private:
 972   /// Determine what action should be taken to legalize the given generic
 973   /// instruction opcode, type-index and type. Requires computeTables to have
 974   /// been called.
 975   ///
 976   /// \returns a pair consisting of the kind of legalization that should be
 977   /// performed and the destination type.
 978   std::pair<LegalizeAction, LLT>
 979   getAspectAction(const InstrAspect &Aspect) const;
 980
 981   /// The SizeAndActionsVec is a representation mapping between all natural
 982   /// numbers and an Action. The natural number represents the bit size of
 983   /// the InstrAspect. For example, for a target with native support for 32-bit
 984   /// and 64-bit additions, you'd express that as:
 985   /// setScalarAction(G_ADD, 0,
 986   ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
 987   ///            {32, Legal},       // bit sizes [32, 33[
 988   ///            {33, WidenScalar}, // bit sizes [33, 64[
 989   ///            {64, Legal},       // bit sizes [64, 65[
 990   ///            {65, NarrowScalar} // bit sizes [65, +inf[
 991   ///           });
 992   /// It may be that only 64-bit pointers are supported on your target:
 993   /// setPointerAction(G_GEP, 0, LLT:pointer(1),
 994   ///           {{1, Unsupported},  // bit sizes [ 1, 63[
 995   ///            {64, Legal},       // bit sizes [64, 65[
 996   ///            {65, Unsupported}, // bit sizes [65, +inf[
 997   ///           });
 998   void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
 999                        const SizeAndActionsVec &SizeAndActions) {
1000     const unsigned OpcodeIdx = Opcode - FirstOp;
1001     SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
1002     setActions(TypeIndex, Actions, SizeAndActions);
1003   }
1004   void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
1005                         const unsigned AddressSpace,
1006                         const SizeAndActionsVec &SizeAndActions) {
1007     const unsigned OpcodeIdx = Opcode - FirstOp;
1008     if (AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace) ==
1009         AddrSpace2PointerActions[OpcodeIdx].end())
1010       AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
1011     SmallVector<SizeAndActionsVec, 1> &Actions =
1012         AddrSpace2PointerActions[OpcodeIdx].find(AddressSpace)->second;
1013     setActions(TypeIndex, Actions, SizeAndActions);
1014   }
1015
1016   /// If an operation on a given vector type (say <M x iN>) isn't explicitly
1017   /// specified, we proceed in 2 stages. First we legalize the underlying scalar
1018   /// (so that there's at least one legal vector with that scalar), then we
1019   /// adjust the number of elements in the vector so that it is legal. The
1020   /// desired action in the first step is controlled by this function.
1021   void setScalarInVectorAction(const unsigned Opcode, const unsigned TypeIndex,
1022                                const SizeAndActionsVec &SizeAndActions) {
1023     unsigned OpcodeIdx = Opcode - FirstOp;
1024     SmallVector<SizeAndActionsVec, 1> &Actions =
1025         ScalarInVectorActions[OpcodeIdx];
1026     setActions(TypeIndex, Actions, SizeAndActions);
1027   }
1028
1029   /// See also setScalarInVectorAction.
1030   /// This function let's you specify the number of elements in a vector that
1031   /// are legal for a legal element size.
1032   void setVectorNumElementAction(const unsigned Opcode,
1033                                  const unsigned TypeIndex,
1034                                  const unsigned ElementSize,
1035                                  const SizeAndActionsVec &SizeAndActions) {
1036     const unsigned OpcodeIdx = Opcode - FirstOp;
1037     if (NumElements2Actions[OpcodeIdx].find(ElementSize) ==
1038         NumElements2Actions[OpcodeIdx].end())
1039       NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
1040     SmallVector<SizeAndActionsVec, 1> &Actions =
1041         NumElements2Actions[OpcodeIdx].find(ElementSize)->second;
1042     setActions(TypeIndex, Actions, SizeAndActions);
1043   }
1044
1045   /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
1046   /// i.e. it's OK if it doesn't start from size 1.
1047   static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
1048     using namespace LegalizeActions;
1049 #ifndef NDEBUG
1050     // The sizes should be in increasing order
1051     int prev_size = -1;
1052     for(auto SizeAndAction: v) {
1053       assert(SizeAndAction.first > prev_size);
1054       prev_size = SizeAndAction.first;
1055     }
1056     // - for every Widen action, there should be a larger bitsize that
1057     //   can be legalized towards (e.g. Legal, Lower, Libcall or Custom
1058     //   action).
1059     // - for every Narrow action, there should be a smaller bitsize that
1060     //   can be legalized towards.
1061     int SmallestNarrowIdx = -1;
1062     int LargestWidenIdx = -1;
1063     int SmallestLegalizableToSameSizeIdx = -1;
1064     int LargestLegalizableToSameSizeIdx = -1;
1065     for(size_t i=0; i<v.size(); ++i) {
1066       switch (v[i].second) {
1067         case FewerElements:
1068         case NarrowScalar:
1069           if (SmallestNarrowIdx == -1)
1070             SmallestNarrowIdx = i;
1071           break;
1072         case WidenScalar:
1073         case MoreElements:
1074           LargestWidenIdx = i;
1075           break;
1076         case Unsupported:
1077           break;
1078         default:
1079           if (SmallestLegalizableToSameSizeIdx == -1)
1080             SmallestLegalizableToSameSizeIdx = i;
1081           LargestLegalizableToSameSizeIdx = i;
1082       }
1083     }
1084     if (SmallestNarrowIdx != -1) {
1085       assert(SmallestLegalizableToSameSizeIdx != -1);
1086       assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
1087     }
1088     if (LargestWidenIdx != -1)
1089       assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
1090 #endif
1091   }
1092
1093   /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
1094   /// from size 1.
1095   static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
1096 #ifndef NDEBUG
1097     // Data structure invariant: The first bit size must be size 1.
1098     assert(v.size() >= 1);
1099     assert(v[0].first == 1);
1100     checkPartialSizeAndActionsVector(v);
1101 #endif
1102   }
1103
1104   /// Sets actions for all bit sizes on a particular generic opcode, type
1105   /// index and scalar or pointer type.
1106   void setActions(unsigned TypeIndex,
1107                   SmallVector<SizeAndActionsVec, 1> &Actions,
1108                   const SizeAndActionsVec &SizeAndActions) {
1109     checkFullSizeAndActionsVector(SizeAndActions);
1110     if (Actions.size() <= TypeIndex)
1111       Actions.resize(TypeIndex + 1);
1112     Actions[TypeIndex] = SizeAndActions;
1113   }
1114
1115   static SizeAndAction findAction(const SizeAndActionsVec &Vec,
1116                                   const uint32_t Size);
1117
1118   /// Returns the next action needed to get the scalar or pointer type closer
1119   /// to being legal
1120   /// E.g. findLegalAction({G_REM, 13}) should return
1121   /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
1122   /// probably be called, which should return (Lower, 32).
1123   /// This is assuming the setScalarAction on G_REM was something like:
1124   /// setScalarAction(G_REM, 0,
1125   ///           {{1, WidenScalar},  // bit sizes [ 1, 31[
1126   ///            {32, Lower},       // bit sizes [32, 33[
1127   ///            {33, NarrowScalar} // bit sizes [65, +inf[
1128   ///           });
1129   std::pair<LegalizeAction, LLT>
1130   findScalarLegalAction(const InstrAspect &Aspect) const;
1131
1132   /// Returns the next action needed towards legalizing the vector type.
1133   std::pair<LegalizeAction, LLT>
1134   findVectorLegalAction(const InstrAspect &Aspect) const;
1135
1136   static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
1137   static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
1138
1139   // Data structures used temporarily during construction of legality data:
1140   using TypeMap = DenseMap<LLT, LegalizeAction>;
1141   SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
1142   SmallVector<SizeChangeStrategy, 1>
1143       ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
1144   SmallVector<SizeChangeStrategy, 1>
1145       VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
1146   bool TablesInitialized;
1147
1148   // Data structures used by getAction:
1149   SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
1150   SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
1151   std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
1152       AddrSpace2PointerActions[LastOp - FirstOp + 1];
1153   std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
1154       NumElements2Actions[LastOp - FirstOp + 1];
1155
1156   LegalizeRuleSet RulesForOpcode[LastOp - FirstOp + 1];
1157 };
1158
1159 #ifndef NDEBUG
1160 /// Checks that MIR is fully legal, returns an illegal instruction if it's not,
1161 /// nullptr otherwise
1162 const MachineInstr *machineFunctionIsIllegal(const MachineFunction &MF);
1163 #endif
1164
1165 } // end namespace llvm.
1166
1167 #endif // LLVM_CODEGEN_GLOBALISEL_LEGALIZERINFO_H