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