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