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

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