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