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