1 //===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- 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 // This file declares the CodeGenDAGPatterns class, which is used to read and 10 // represent the patterns present in a .td file for instructions. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H 15 #define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H 16 17 #include "CodeGenIntrinsics.h" 18 #include "CodeGenTarget.h" 19 #include "SDNodeProperties.h" 20 #include "llvm/ADT/IntrusiveRefCntPtr.h" 21 #include "llvm/ADT/MapVector.h" 22 #include "llvm/ADT/PointerUnion.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/ADT/StringMap.h" 25 #include "llvm/ADT/StringSet.h" 26 #include "llvm/ADT/Twine.h" 27 #include "llvm/Support/ErrorHandling.h" 28 #include "llvm/Support/MathExtras.h" 29 #include "llvm/TableGen/Record.h" 30 #include <algorithm> 31 #include <array> 32 #include <functional> 33 #include <map> 34 #include <numeric> 35 #include <vector> 36 37 namespace llvm { 38 39 class Init; 40 class ListInit; 41 class DagInit; 42 class SDNodeInfo; 43 class TreePattern; 44 class TreePatternNode; 45 class CodeGenDAGPatterns; 46 47 /// Shared pointer for TreePatternNode. 48 using TreePatternNodePtr = IntrusiveRefCntPtr<TreePatternNode>; 49 50 /// This represents a set of MVTs. Since the underlying type for the MVT 51 /// is uint8_t, there are at most 256 values. To reduce the number of memory 52 /// allocations and deallocations, represent the set as a sequence of bits. 53 /// To reduce the allocations even further, make MachineValueTypeSet own 54 /// the storage and use std::array as the bit container. 55 struct MachineValueTypeSet { 56 static_assert(std::is_same<std::underlying_type_t<MVT::SimpleValueType>, 57 uint8_t>::value, 58 "Change uint8_t here to the SimpleValueType's type"); 59 static unsigned constexpr Capacity = std::numeric_limits<uint8_t>::max()+1; 60 using WordType = uint64_t; 61 static unsigned constexpr WordWidth = CHAR_BIT*sizeof(WordType); 62 static unsigned constexpr NumWords = Capacity/WordWidth; 63 static_assert(NumWords*WordWidth == Capacity, 64 "Capacity should be a multiple of WordWidth"); 65 66 LLVM_ATTRIBUTE_ALWAYS_INLINE 67 MachineValueTypeSet() { 68 clear(); 69 } 70 71 LLVM_ATTRIBUTE_ALWAYS_INLINE 72 unsigned size() const { 73 unsigned Count = 0; 74 for (WordType W : Words) 75 Count += llvm::popcount(W); 76 return Count; 77 } 78 LLVM_ATTRIBUTE_ALWAYS_INLINE 79 void clear() { 80 std::memset(Words.data(), 0, NumWords*sizeof(WordType)); 81 } 82 LLVM_ATTRIBUTE_ALWAYS_INLINE 83 bool empty() const { 84 for (WordType W : Words) 85 if (W != 0) 86 return false; 87 return true; 88 } 89 LLVM_ATTRIBUTE_ALWAYS_INLINE 90 unsigned count(MVT T) const { 91 return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1; 92 } 93 std::pair<MachineValueTypeSet&,bool> insert(MVT T) { 94 bool V = count(T.SimpleTy); 95 Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth); 96 return {*this, V}; 97 } 98 MachineValueTypeSet &insert(const MachineValueTypeSet &S) { 99 for (unsigned i = 0; i != NumWords; ++i) 100 Words[i] |= S.Words[i]; 101 return *this; 102 } 103 LLVM_ATTRIBUTE_ALWAYS_INLINE 104 void erase(MVT T) { 105 Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth)); 106 } 107 108 void writeToStream(raw_ostream &OS) const; 109 110 struct const_iterator { 111 // Some implementations of the C++ library require these traits to be 112 // defined. 113 using iterator_category = std::forward_iterator_tag; 114 using value_type = MVT; 115 using difference_type = ptrdiff_t; 116 using pointer = const MVT*; 117 using reference = const MVT&; 118 119 LLVM_ATTRIBUTE_ALWAYS_INLINE 120 MVT operator*() const { 121 assert(Pos != Capacity); 122 return MVT::SimpleValueType(Pos); 123 } 124 LLVM_ATTRIBUTE_ALWAYS_INLINE 125 const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) { 126 Pos = End ? Capacity : find_from_pos(0); 127 } 128 LLVM_ATTRIBUTE_ALWAYS_INLINE 129 const_iterator &operator++() { 130 assert(Pos != Capacity); 131 Pos = find_from_pos(Pos+1); 132 return *this; 133 } 134 135 LLVM_ATTRIBUTE_ALWAYS_INLINE 136 bool operator==(const const_iterator &It) const { 137 return Set == It.Set && Pos == It.Pos; 138 } 139 LLVM_ATTRIBUTE_ALWAYS_INLINE 140 bool operator!=(const const_iterator &It) const { 141 return !operator==(It); 142 } 143 144 private: 145 unsigned find_from_pos(unsigned P) const { 146 unsigned SkipWords = P / WordWidth; 147 unsigned SkipBits = P % WordWidth; 148 unsigned Count = SkipWords * WordWidth; 149 150 // If P is in the middle of a word, process it manually here, because 151 // the trailing bits need to be masked off to use findFirstSet. 152 if (SkipBits != 0) { 153 WordType W = Set->Words[SkipWords]; 154 W &= maskLeadingOnes<WordType>(WordWidth-SkipBits); 155 if (W != 0) 156 return Count + llvm::countr_zero(W); 157 Count += WordWidth; 158 SkipWords++; 159 } 160 161 for (unsigned i = SkipWords; i != NumWords; ++i) { 162 WordType W = Set->Words[i]; 163 if (W != 0) 164 return Count + llvm::countr_zero(W); 165 Count += WordWidth; 166 } 167 return Capacity; 168 } 169 170 const MachineValueTypeSet *Set; 171 unsigned Pos; 172 }; 173 174 LLVM_ATTRIBUTE_ALWAYS_INLINE 175 const_iterator begin() const { return const_iterator(this, false); } 176 LLVM_ATTRIBUTE_ALWAYS_INLINE 177 const_iterator end() const { return const_iterator(this, true); } 178 179 LLVM_ATTRIBUTE_ALWAYS_INLINE 180 bool operator==(const MachineValueTypeSet &S) const { 181 return Words == S.Words; 182 } 183 LLVM_ATTRIBUTE_ALWAYS_INLINE 184 bool operator!=(const MachineValueTypeSet &S) const { 185 return !operator==(S); 186 } 187 188 private: 189 friend struct const_iterator; 190 std::array<WordType,NumWords> Words; 191 }; 192 193 raw_ostream &operator<<(raw_ostream &OS, const MachineValueTypeSet &T); 194 195 struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> { 196 using SetType = MachineValueTypeSet; 197 unsigned AddrSpace = std::numeric_limits<unsigned>::max(); 198 199 TypeSetByHwMode() = default; 200 TypeSetByHwMode(const TypeSetByHwMode &VTS) = default; 201 TypeSetByHwMode &operator=(const TypeSetByHwMode &) = default; 202 TypeSetByHwMode(MVT::SimpleValueType VT) 203 : TypeSetByHwMode(ValueTypeByHwMode(VT)) {} 204 TypeSetByHwMode(ValueTypeByHwMode VT) 205 : TypeSetByHwMode(ArrayRef<ValueTypeByHwMode>(&VT, 1)) {} 206 TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList); 207 208 SetType &getOrCreate(unsigned Mode) { 209 return Map[Mode]; 210 } 211 212 bool isValueTypeByHwMode(bool AllowEmpty) const; 213 ValueTypeByHwMode getValueTypeByHwMode() const; 214 215 LLVM_ATTRIBUTE_ALWAYS_INLINE 216 bool isMachineValueType() const { 217 return isSimple() && getSimple().size() == 1; 218 } 219 220 LLVM_ATTRIBUTE_ALWAYS_INLINE 221 MVT getMachineValueType() const { 222 assert(isMachineValueType()); 223 return *getSimple().begin(); 224 } 225 226 bool isPossible() const; 227 228 bool isPointer() const { 229 return getValueTypeByHwMode().isPointer(); 230 } 231 232 unsigned getPtrAddrSpace() const { 233 assert(isPointer()); 234 return getValueTypeByHwMode().PtrAddrSpace; 235 } 236 237 bool insert(const ValueTypeByHwMode &VVT); 238 bool constrain(const TypeSetByHwMode &VTS); 239 template <typename Predicate> bool constrain(Predicate P); 240 template <typename Predicate> 241 bool assign_if(const TypeSetByHwMode &VTS, Predicate P); 242 243 void writeToStream(raw_ostream &OS) const; 244 245 bool operator==(const TypeSetByHwMode &VTS) const; 246 bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); } 247 248 void dump() const; 249 bool validate() const; 250 251 private: 252 unsigned PtrAddrSpace = std::numeric_limits<unsigned>::max(); 253 /// Intersect two sets. Return true if anything has changed. 254 bool intersect(SetType &Out, const SetType &In); 255 }; 256 257 raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T); 258 259 struct TypeInfer { 260 TypeInfer(TreePattern &T) : TP(T) {} 261 262 bool isConcrete(const TypeSetByHwMode &VTS, bool AllowEmpty) const { 263 return VTS.isValueTypeByHwMode(AllowEmpty); 264 } 265 ValueTypeByHwMode getConcrete(const TypeSetByHwMode &VTS, 266 bool AllowEmpty) const { 267 assert(VTS.isValueTypeByHwMode(AllowEmpty)); 268 return VTS.getValueTypeByHwMode(); 269 } 270 271 /// The protocol in the following functions (Merge*, force*, Enforce*, 272 /// expand*) is to return "true" if a change has been made, "false" 273 /// otherwise. 274 275 bool MergeInTypeInfo(TypeSetByHwMode &Out, const TypeSetByHwMode &In) const; 276 bool MergeInTypeInfo(TypeSetByHwMode &Out, MVT::SimpleValueType InVT) const { 277 return MergeInTypeInfo(Out, TypeSetByHwMode(InVT)); 278 } 279 bool MergeInTypeInfo(TypeSetByHwMode &Out, ValueTypeByHwMode InVT) const { 280 return MergeInTypeInfo(Out, TypeSetByHwMode(InVT)); 281 } 282 283 /// Reduce the set \p Out to have at most one element for each mode. 284 bool forceArbitrary(TypeSetByHwMode &Out); 285 286 /// The following four functions ensure that upon return the set \p Out 287 /// will only contain types of the specified kind: integer, floating-point, 288 /// scalar, or vector. 289 /// If \p Out is empty, all legal types of the specified kind will be added 290 /// to it. Otherwise, all types that are not of the specified kind will be 291 /// removed from \p Out. 292 bool EnforceInteger(TypeSetByHwMode &Out); 293 bool EnforceFloatingPoint(TypeSetByHwMode &Out); 294 bool EnforceScalar(TypeSetByHwMode &Out); 295 bool EnforceVector(TypeSetByHwMode &Out); 296 297 /// If \p Out is empty, fill it with all legal types. Otherwise, leave it 298 /// unchanged. 299 bool EnforceAny(TypeSetByHwMode &Out); 300 /// Make sure that for each type in \p Small, there exists a larger type 301 /// in \p Big. \p SmallIsVT indicates that this is being called for 302 /// SDTCisVTSmallerThanOp. In that case the TypeSetByHwMode is re-created for 303 /// each call and needs special consideration in how we detect changes. 304 bool EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big, 305 bool SmallIsVT = false); 306 /// 1. Ensure that for each type T in \p Vec, T is a vector type, and that 307 /// for each type U in \p Elem, U is a scalar type. 308 /// 2. Ensure that for each (scalar) type U in \p Elem, there exists a 309 /// (vector) type T in \p Vec, such that U is the element type of T. 310 bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, TypeSetByHwMode &Elem); 311 bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, 312 const ValueTypeByHwMode &VVT); 313 /// Ensure that for each type T in \p Sub, T is a vector type, and there 314 /// exists a type U in \p Vec such that U is a vector type with the same 315 /// element type as T and at least as many elements as T. 316 bool EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec, 317 TypeSetByHwMode &Sub); 318 /// 1. Ensure that \p V has a scalar type iff \p W has a scalar type. 319 /// 2. Ensure that for each vector type T in \p V, there exists a vector 320 /// type U in \p W, such that T and U have the same number of elements. 321 /// 3. Ensure that for each vector type U in \p W, there exists a vector 322 /// type T in \p V, such that T and U have the same number of elements 323 /// (reverse of 2). 324 bool EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W); 325 /// 1. Ensure that for each type T in \p A, there exists a type U in \p B, 326 /// such that T and U have equal size in bits. 327 /// 2. Ensure that for each type U in \p B, there exists a type T in \p A 328 /// such that T and U have equal size in bits (reverse of 1). 329 bool EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B); 330 331 /// For each overloaded type (i.e. of form *Any), replace it with the 332 /// corresponding subset of legal, specific types. 333 void expandOverloads(TypeSetByHwMode &VTS) const; 334 void expandOverloads(TypeSetByHwMode::SetType &Out, 335 const TypeSetByHwMode::SetType &Legal) const; 336 337 struct ValidateOnExit { 338 ValidateOnExit(const TypeSetByHwMode &T, const TypeInfer &TI) 339 : Infer(TI), VTS(T) {} 340 ~ValidateOnExit(); 341 const TypeInfer &Infer; 342 const TypeSetByHwMode &VTS; 343 }; 344 345 struct SuppressValidation { 346 SuppressValidation(TypeInfer &TI) : Infer(TI), SavedValidate(TI.Validate) { 347 Infer.Validate = false; 348 } 349 ~SuppressValidation() { 350 Infer.Validate = SavedValidate; 351 } 352 TypeInfer &Infer; 353 bool SavedValidate; 354 }; 355 356 TreePattern &TP; 357 bool Validate = true; // Indicate whether to validate types. 358 359 private: 360 const TypeSetByHwMode &getLegalTypes() const; 361 362 /// Cached legal types (in default mode). 363 mutable bool LegalTypesCached = false; 364 mutable TypeSetByHwMode LegalCache; 365 }; 366 367 /// Set type used to track multiply used variables in patterns 368 typedef StringSet<> MultipleUseVarSet; 369 370 /// SDTypeConstraint - This is a discriminated union of constraints, 371 /// corresponding to the SDTypeConstraint tablegen class in Target.td. 372 struct SDTypeConstraint { 373 SDTypeConstraint(Record *R, const CodeGenHwModes &CGH); 374 375 unsigned OperandNo; // The operand # this constraint applies to. 376 enum { 377 SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs, 378 SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec, 379 SDTCisSubVecOfVec, SDTCVecEltisVT, SDTCisSameNumEltsAs, SDTCisSameSizeAs 380 } ConstraintType; 381 382 union { // The discriminated union. 383 struct { 384 unsigned OtherOperandNum; 385 } SDTCisSameAs_Info; 386 struct { 387 unsigned OtherOperandNum; 388 } SDTCisVTSmallerThanOp_Info; 389 struct { 390 unsigned BigOperandNum; 391 } SDTCisOpSmallerThanOp_Info; 392 struct { 393 unsigned OtherOperandNum; 394 } SDTCisEltOfVec_Info; 395 struct { 396 unsigned OtherOperandNum; 397 } SDTCisSubVecOfVec_Info; 398 struct { 399 unsigned OtherOperandNum; 400 } SDTCisSameNumEltsAs_Info; 401 struct { 402 unsigned OtherOperandNum; 403 } SDTCisSameSizeAs_Info; 404 } x; 405 406 // The VT for SDTCisVT and SDTCVecEltisVT. 407 // Must not be in the union because it has a non-trivial destructor. 408 ValueTypeByHwMode VVT; 409 410 /// ApplyTypeConstraint - Given a node in a pattern, apply this type 411 /// constraint to the nodes operands. This returns true if it makes a 412 /// change, false otherwise. If a type contradiction is found, an error 413 /// is flagged. 414 bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo, 415 TreePattern &TP) const; 416 }; 417 418 /// ScopedName - A name of a node associated with a "scope" that indicates 419 /// the context (e.g. instance of Pattern or PatFrag) in which the name was 420 /// used. This enables substitution of pattern fragments while keeping track 421 /// of what name(s) were originally given to various nodes in the tree. 422 class ScopedName { 423 unsigned Scope; 424 std::string Identifier; 425 public: 426 ScopedName(unsigned Scope, StringRef Identifier) 427 : Scope(Scope), Identifier(std::string(Identifier)) { 428 assert(Scope != 0 && 429 "Scope == 0 is used to indicate predicates without arguments"); 430 } 431 432 unsigned getScope() const { return Scope; } 433 const std::string &getIdentifier() const { return Identifier; } 434 435 bool operator==(const ScopedName &o) const; 436 bool operator!=(const ScopedName &o) const; 437 }; 438 439 /// SDNodeInfo - One of these records is created for each SDNode instance in 440 /// the target .td file. This represents the various dag nodes we will be 441 /// processing. 442 class SDNodeInfo { 443 Record *Def; 444 StringRef EnumName; 445 StringRef SDClassName; 446 unsigned Properties; 447 unsigned NumResults; 448 int NumOperands; 449 std::vector<SDTypeConstraint> TypeConstraints; 450 public: 451 // Parse the specified record. 452 SDNodeInfo(Record *R, const CodeGenHwModes &CGH); 453 454 unsigned getNumResults() const { return NumResults; } 455 456 /// getNumOperands - This is the number of operands required or -1 if 457 /// variadic. 458 int getNumOperands() const { return NumOperands; } 459 Record *getRecord() const { return Def; } 460 StringRef getEnumName() const { return EnumName; } 461 StringRef getSDClassName() const { return SDClassName; } 462 463 const std::vector<SDTypeConstraint> &getTypeConstraints() const { 464 return TypeConstraints; 465 } 466 467 /// getKnownType - If the type constraints on this node imply a fixed type 468 /// (e.g. all stores return void, etc), then return it as an 469 /// MVT::SimpleValueType. Otherwise, return MVT::Other. 470 MVT::SimpleValueType getKnownType(unsigned ResNo) const; 471 472 /// hasProperty - Return true if this node has the specified property. 473 /// 474 bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); } 475 476 /// ApplyTypeConstraints - Given a node in a pattern, apply the type 477 /// constraints for this node to the operands of the node. This returns 478 /// true if it makes a change, false otherwise. If a type contradiction is 479 /// found, an error is flagged. 480 bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const; 481 }; 482 483 /// TreePredicateFn - This is an abstraction that represents the predicates on 484 /// a PatFrag node. This is a simple one-word wrapper around a pointer to 485 /// provide nice accessors. 486 class TreePredicateFn { 487 /// PatFragRec - This is the TreePattern for the PatFrag that we 488 /// originally came from. 489 TreePattern *PatFragRec; 490 public: 491 /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag. 492 TreePredicateFn(TreePattern *N); 493 494 495 TreePattern *getOrigPatFragRecord() const { return PatFragRec; } 496 497 /// isAlwaysTrue - Return true if this is a noop predicate. 498 bool isAlwaysTrue() const; 499 500 bool isImmediatePattern() const { return hasImmCode(); } 501 502 /// getImmediatePredicateCode - Return the code that evaluates this pattern if 503 /// this is an immediate predicate. It is an error to call this on a 504 /// non-immediate pattern. 505 std::string getImmediatePredicateCode() const { 506 std::string Result = getImmCode(); 507 assert(!Result.empty() && "Isn't an immediate pattern!"); 508 return Result; 509 } 510 511 bool operator==(const TreePredicateFn &RHS) const { 512 return PatFragRec == RHS.PatFragRec; 513 } 514 515 bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); } 516 517 /// Return the name to use in the generated code to reference this, this is 518 /// "Predicate_foo" if from a pattern fragment "foo". 519 std::string getFnName() const; 520 521 /// getCodeToRunOnSDNode - Return the code for the function body that 522 /// evaluates this predicate. The argument is expected to be in "Node", 523 /// not N. This handles casting and conversion to a concrete node type as 524 /// appropriate. 525 std::string getCodeToRunOnSDNode() const; 526 527 /// Get the data type of the argument to getImmediatePredicateCode(). 528 StringRef getImmType() const; 529 530 /// Get a string that describes the type returned by getImmType() but is 531 /// usable as part of an identifier. 532 StringRef getImmTypeIdentifier() const; 533 534 // Predicate code uses the PatFrag's captured operands. 535 bool usesOperands() const; 536 537 // Check if the HasNoUse predicate is set. 538 bool hasNoUse() const; 539 540 // Is the desired predefined predicate for a load? 541 bool isLoad() const; 542 // Is the desired predefined predicate for a store? 543 bool isStore() const; 544 // Is the desired predefined predicate for an atomic? 545 bool isAtomic() const; 546 547 /// Is this predicate the predefined unindexed load predicate? 548 /// Is this predicate the predefined unindexed store predicate? 549 bool isUnindexed() const; 550 /// Is this predicate the predefined non-extending load predicate? 551 bool isNonExtLoad() const; 552 /// Is this predicate the predefined any-extend load predicate? 553 bool isAnyExtLoad() const; 554 /// Is this predicate the predefined sign-extend load predicate? 555 bool isSignExtLoad() const; 556 /// Is this predicate the predefined zero-extend load predicate? 557 bool isZeroExtLoad() const; 558 /// Is this predicate the predefined non-truncating store predicate? 559 bool isNonTruncStore() const; 560 /// Is this predicate the predefined truncating store predicate? 561 bool isTruncStore() const; 562 563 /// Is this predicate the predefined monotonic atomic predicate? 564 bool isAtomicOrderingMonotonic() const; 565 /// Is this predicate the predefined acquire atomic predicate? 566 bool isAtomicOrderingAcquire() const; 567 /// Is this predicate the predefined release atomic predicate? 568 bool isAtomicOrderingRelease() const; 569 /// Is this predicate the predefined acquire-release atomic predicate? 570 bool isAtomicOrderingAcquireRelease() const; 571 /// Is this predicate the predefined sequentially consistent atomic predicate? 572 bool isAtomicOrderingSequentiallyConsistent() const; 573 574 /// Is this predicate the predefined acquire-or-stronger atomic predicate? 575 bool isAtomicOrderingAcquireOrStronger() const; 576 /// Is this predicate the predefined weaker-than-acquire atomic predicate? 577 bool isAtomicOrderingWeakerThanAcquire() const; 578 579 /// Is this predicate the predefined release-or-stronger atomic predicate? 580 bool isAtomicOrderingReleaseOrStronger() const; 581 /// Is this predicate the predefined weaker-than-release atomic predicate? 582 bool isAtomicOrderingWeakerThanRelease() const; 583 584 /// If non-null, indicates that this predicate is a predefined memory VT 585 /// predicate for a load/store and returns the ValueType record for the memory VT. 586 Record *getMemoryVT() const; 587 /// If non-null, indicates that this predicate is a predefined memory VT 588 /// predicate (checking only the scalar type) for load/store and returns the 589 /// ValueType record for the memory VT. 590 Record *getScalarMemoryVT() const; 591 592 ListInit *getAddressSpaces() const; 593 int64_t getMinAlignment() const; 594 595 // If true, indicates that GlobalISel-based C++ code was supplied. 596 bool hasGISelPredicateCode() const; 597 std::string getGISelPredicateCode() const; 598 599 private: 600 bool hasPredCode() const; 601 bool hasImmCode() const; 602 std::string getPredCode() const; 603 std::string getImmCode() const; 604 bool immCodeUsesAPInt() const; 605 bool immCodeUsesAPFloat() const; 606 607 bool isPredefinedPredicateEqualTo(StringRef Field, bool Value) const; 608 }; 609 610 struct TreePredicateCall { 611 TreePredicateFn Fn; 612 613 // Scope -- unique identifier for retrieving named arguments. 0 is used when 614 // the predicate does not use named arguments. 615 unsigned Scope; 616 617 TreePredicateCall(const TreePredicateFn &Fn, unsigned Scope) 618 : Fn(Fn), Scope(Scope) {} 619 620 bool operator==(const TreePredicateCall &o) const { 621 return Fn == o.Fn && Scope == o.Scope; 622 } 623 bool operator!=(const TreePredicateCall &o) const { 624 return !(*this == o); 625 } 626 }; 627 628 class TreePatternNode : public RefCountedBase<TreePatternNode> { 629 /// The type of each node result. Before and during type inference, each 630 /// result may be a set of possible types. After (successful) type inference, 631 /// each is a single concrete type. 632 std::vector<TypeSetByHwMode> Types; 633 634 /// The index of each result in results of the pattern. 635 std::vector<unsigned> ResultPerm; 636 637 /// OperatorOrVal - The Record for the operator if this is an interior node 638 /// (not a leaf) or the init value (e.g. the "GPRC" record, or "7") for a 639 /// leaf. 640 PointerUnion<Record *, Init *> OperatorOrVal; 641 642 /// Name - The name given to this node with the :$foo notation. 643 /// 644 std::string Name; 645 646 std::vector<ScopedName> NamesAsPredicateArg; 647 648 /// PredicateCalls - The predicate functions to execute on this node to check 649 /// for a match. If this list is empty, no predicate is involved. 650 std::vector<TreePredicateCall> PredicateCalls; 651 652 /// TransformFn - The transformation function to execute on this node before 653 /// it can be substituted into the resulting instruction on a pattern match. 654 Record *TransformFn; 655 656 std::vector<TreePatternNodePtr> Children; 657 658 /// If this was instantiated from a PatFrag node, and the PatFrag was derived 659 /// from "GISelFlags": the original Record derived from GISelFlags. 660 const Record *GISelFlags = nullptr; 661 662 public: 663 TreePatternNode(Record *Op, std::vector<TreePatternNodePtr> Ch, 664 unsigned NumResults) 665 : OperatorOrVal(Op), TransformFn(nullptr), Children(std::move(Ch)) { 666 Types.resize(NumResults); 667 ResultPerm.resize(NumResults); 668 std::iota(ResultPerm.begin(), ResultPerm.end(), 0); 669 } 670 TreePatternNode(Init *val, unsigned NumResults) // leaf ctor 671 : OperatorOrVal(val), TransformFn(nullptr) { 672 Types.resize(NumResults); 673 ResultPerm.resize(NumResults); 674 std::iota(ResultPerm.begin(), ResultPerm.end(), 0); 675 } 676 677 bool hasName() const { return !Name.empty(); } 678 const std::string &getName() const { return Name; } 679 void setName(StringRef N) { Name.assign(N.begin(), N.end()); } 680 681 const std::vector<ScopedName> &getNamesAsPredicateArg() const { 682 return NamesAsPredicateArg; 683 } 684 void setNamesAsPredicateArg(const std::vector<ScopedName>& Names) { 685 NamesAsPredicateArg = Names; 686 } 687 void addNameAsPredicateArg(const ScopedName &N) { 688 NamesAsPredicateArg.push_back(N); 689 } 690 691 bool isLeaf() const { return isa<Init *>(OperatorOrVal); } 692 693 // Type accessors. 694 unsigned getNumTypes() const { return Types.size(); } 695 ValueTypeByHwMode getType(unsigned ResNo) const { 696 return Types[ResNo].getValueTypeByHwMode(); 697 } 698 const std::vector<TypeSetByHwMode> &getExtTypes() const { return Types; } 699 const TypeSetByHwMode &getExtType(unsigned ResNo) const { 700 return Types[ResNo]; 701 } 702 TypeSetByHwMode &getExtType(unsigned ResNo) { return Types[ResNo]; } 703 void setType(unsigned ResNo, const TypeSetByHwMode &T) { Types[ResNo] = T; } 704 MVT::SimpleValueType getSimpleType(unsigned ResNo) const { 705 return Types[ResNo].getMachineValueType().SimpleTy; 706 } 707 708 bool hasConcreteType(unsigned ResNo) const { 709 return Types[ResNo].isValueTypeByHwMode(false); 710 } 711 bool isTypeCompletelyUnknown(unsigned ResNo, TreePattern &TP) const { 712 return Types[ResNo].empty(); 713 } 714 715 unsigned getNumResults() const { return ResultPerm.size(); } 716 unsigned getResultIndex(unsigned ResNo) const { return ResultPerm[ResNo]; } 717 void setResultIndex(unsigned ResNo, unsigned RI) { ResultPerm[ResNo] = RI; } 718 719 Init *getLeafValue() const { 720 assert(isLeaf()); 721 return cast<Init *>(OperatorOrVal); 722 } 723 Record *getOperator() const { 724 assert(!isLeaf()); 725 return cast<Record *>(OperatorOrVal); 726 } 727 728 unsigned getNumChildren() const { return Children.size(); } 729 const TreePatternNode *getChild(unsigned N) const { 730 return Children[N].get(); 731 } 732 TreePatternNode *getChild(unsigned N) { return Children[N].get(); } 733 const TreePatternNodePtr &getChildShared(unsigned N) const { 734 return Children[N]; 735 } 736 TreePatternNodePtr &getChildSharedPtr(unsigned N) { 737 return Children[N]; 738 } 739 void setChild(unsigned i, TreePatternNodePtr N) { Children[i] = N; } 740 741 /// hasChild - Return true if N is any of our children. 742 bool hasChild(const TreePatternNode *N) const { 743 for (unsigned i = 0, e = Children.size(); i != e; ++i) 744 if (Children[i].get() == N) 745 return true; 746 return false; 747 } 748 749 bool hasProperTypeByHwMode() const; 750 bool hasPossibleType() const; 751 bool setDefaultMode(unsigned Mode); 752 753 bool hasAnyPredicate() const { return !PredicateCalls.empty(); } 754 755 const std::vector<TreePredicateCall> &getPredicateCalls() const { 756 return PredicateCalls; 757 } 758 void clearPredicateCalls() { PredicateCalls.clear(); } 759 void setPredicateCalls(const std::vector<TreePredicateCall> &Calls) { 760 assert(PredicateCalls.empty() && "Overwriting non-empty predicate list!"); 761 PredicateCalls = Calls; 762 } 763 void addPredicateCall(const TreePredicateCall &Call) { 764 assert(!Call.Fn.isAlwaysTrue() && "Empty predicate string!"); 765 assert(!is_contained(PredicateCalls, Call) && "predicate applied recursively"); 766 PredicateCalls.push_back(Call); 767 } 768 void addPredicateCall(const TreePredicateFn &Fn, unsigned Scope) { 769 assert((Scope != 0) == Fn.usesOperands()); 770 addPredicateCall(TreePredicateCall(Fn, Scope)); 771 } 772 773 Record *getTransformFn() const { return TransformFn; } 774 void setTransformFn(Record *Fn) { TransformFn = Fn; } 775 776 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 777 /// CodeGenIntrinsic information for it, otherwise return a null pointer. 778 const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const; 779 780 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern, 781 /// return the ComplexPattern information, otherwise return null. 782 const ComplexPattern * 783 getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const; 784 785 /// Returns the number of MachineInstr operands that would be produced by this 786 /// node if it mapped directly to an output Instruction's 787 /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it 788 /// for Operands; otherwise 1. 789 unsigned getNumMIResults(const CodeGenDAGPatterns &CGP) const; 790 791 /// NodeHasProperty - Return true if this node has the specified property. 792 bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 793 794 /// TreeHasProperty - Return true if any node in this tree has the specified 795 /// property. 796 bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const; 797 798 /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is 799 /// marked isCommutative. 800 bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const; 801 802 void setGISelFlagsRecord(const Record *R) { GISelFlags = R; } 803 const Record *getGISelFlagsRecord() const { return GISelFlags; } 804 805 void print(raw_ostream &OS) const; 806 void dump() const; 807 808 public: // Higher level manipulation routines. 809 810 /// clone - Return a new copy of this tree. 811 /// 812 TreePatternNodePtr clone() const; 813 814 /// RemoveAllTypes - Recursively strip all the types of this tree. 815 void RemoveAllTypes(); 816 817 /// isIsomorphicTo - Return true if this node is recursively isomorphic to 818 /// the specified node. For this comparison, all of the state of the node 819 /// is considered, except for the assigned name. Nodes with differing names 820 /// that are otherwise identical are considered isomorphic. 821 bool isIsomorphicTo(const TreePatternNode *N, 822 const MultipleUseVarSet &DepVars) const; 823 824 /// SubstituteFormalArguments - Replace the formal arguments in this tree 825 /// with actual values specified by ArgMap. 826 void 827 SubstituteFormalArguments(std::map<std::string, TreePatternNodePtr> &ArgMap); 828 829 /// InlinePatternFragments - If \p T pattern refers to any pattern 830 /// fragments, return the set of inlined versions (this can be more than 831 /// one if a PatFrags record has multiple alternatives). 832 void InlinePatternFragments(TreePattern &TP, 833 std::vector<TreePatternNodePtr> &OutAlternatives); 834 835 /// ApplyTypeConstraints - Apply all of the type constraints relevant to 836 /// this node and its children in the tree. This returns true if it makes a 837 /// change, false otherwise. If a type contradiction is found, flag an error. 838 bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters); 839 840 /// UpdateNodeType - Set the node type of N to VT if VT contains 841 /// information. If N already contains a conflicting type, then flag an 842 /// error. This returns true if any information was updated. 843 /// 844 bool UpdateNodeType(unsigned ResNo, const TypeSetByHwMode &InTy, 845 TreePattern &TP); 846 bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy, 847 TreePattern &TP); 848 bool UpdateNodeType(unsigned ResNo, ValueTypeByHwMode InTy, 849 TreePattern &TP); 850 851 // Update node type with types inferred from an instruction operand or result 852 // def from the ins/outs lists. 853 // Return true if the type changed. 854 bool UpdateNodeTypeFromInst(unsigned ResNo, Record *Operand, TreePattern &TP); 855 856 /// ContainsUnresolvedType - Return true if this tree contains any 857 /// unresolved types. 858 bool ContainsUnresolvedType(TreePattern &TP) const; 859 860 /// canPatternMatch - If it is impossible for this pattern to match on this 861 /// target, fill in Reason and return false. Otherwise, return true. 862 bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP); 863 }; 864 865 inline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) { 866 TPN.print(OS); 867 return OS; 868 } 869 870 /// TreePattern - Represent a pattern, used for instructions, pattern 871 /// fragments, etc. 872 /// 873 class TreePattern { 874 /// Trees - The list of pattern trees which corresponds to this pattern. 875 /// Note that PatFrag's only have a single tree. 876 /// 877 std::vector<TreePatternNodePtr> Trees; 878 879 /// NamedNodes - This is all of the nodes that have names in the trees in this 880 /// pattern. 881 StringMap<SmallVector<TreePatternNode *, 1>> NamedNodes; 882 883 /// TheRecord - The actual TableGen record corresponding to this pattern. 884 /// 885 Record *TheRecord; 886 887 /// Args - This is a list of all of the arguments to this pattern (for 888 /// PatFrag patterns), which are the 'node' markers in this pattern. 889 std::vector<std::string> Args; 890 891 /// CDP - the top-level object coordinating this madness. 892 /// 893 CodeGenDAGPatterns &CDP; 894 895 /// isInputPattern - True if this is an input pattern, something to match. 896 /// False if this is an output pattern, something to emit. 897 bool isInputPattern; 898 899 /// hasError - True if the currently processed nodes have unresolvable types 900 /// or other non-fatal errors 901 bool HasError; 902 903 /// It's important that the usage of operands in ComplexPatterns is 904 /// consistent: each named operand can be defined by at most one 905 /// ComplexPattern. This records the ComplexPattern instance and the operand 906 /// number for each operand encountered in a ComplexPattern to aid in that 907 /// check. 908 StringMap<std::pair<Record *, unsigned>> ComplexPatternOperands; 909 910 TypeInfer Infer; 911 912 public: 913 914 /// TreePattern constructor - Parse the specified DagInits into the 915 /// current record. 916 TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 917 CodeGenDAGPatterns &ise); 918 TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 919 CodeGenDAGPatterns &ise); 920 TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput, 921 CodeGenDAGPatterns &ise); 922 923 /// getTrees - Return the tree patterns which corresponds to this pattern. 924 /// 925 const std::vector<TreePatternNodePtr> &getTrees() const { return Trees; } 926 unsigned getNumTrees() const { return Trees.size(); } 927 const TreePatternNodePtr &getTree(unsigned i) const { return Trees[i]; } 928 void setTree(unsigned i, TreePatternNodePtr Tree) { Trees[i] = Tree; } 929 const TreePatternNodePtr &getOnlyTree() const { 930 assert(Trees.size() == 1 && "Doesn't have exactly one pattern!"); 931 return Trees[0]; 932 } 933 934 const StringMap<SmallVector<TreePatternNode *, 1>> &getNamedNodesMap() { 935 if (NamedNodes.empty()) 936 ComputeNamedNodes(); 937 return NamedNodes; 938 } 939 940 /// getRecord - Return the actual TableGen record corresponding to this 941 /// pattern. 942 /// 943 Record *getRecord() const { return TheRecord; } 944 945 unsigned getNumArgs() const { return Args.size(); } 946 const std::string &getArgName(unsigned i) const { 947 assert(i < Args.size() && "Argument reference out of range!"); 948 return Args[i]; 949 } 950 std::vector<std::string> &getArgList() { return Args; } 951 952 CodeGenDAGPatterns &getDAGPatterns() const { return CDP; } 953 954 /// InlinePatternFragments - If this pattern refers to any pattern 955 /// fragments, inline them into place, giving us a pattern without any 956 /// PatFrags references. This may increase the number of trees in the 957 /// pattern if a PatFrags has multiple alternatives. 958 void InlinePatternFragments() { 959 std::vector<TreePatternNodePtr> Copy; 960 Trees.swap(Copy); 961 for (const TreePatternNodePtr &C : Copy) 962 C->InlinePatternFragments(*this, Trees); 963 } 964 965 /// InferAllTypes - Infer/propagate as many types throughout the expression 966 /// patterns as possible. Return true if all types are inferred, false 967 /// otherwise. Bail out if a type contradiction is found. 968 bool InferAllTypes( 969 const StringMap<SmallVector<TreePatternNode *, 1>> *NamedTypes = nullptr); 970 971 /// error - If this is the first error in the current resolution step, 972 /// print it and set the error flag. Otherwise, continue silently. 973 void error(const Twine &Msg); 974 bool hasError() const { 975 return HasError; 976 } 977 void resetError() { 978 HasError = false; 979 } 980 981 TypeInfer &getInfer() { return Infer; } 982 983 void print(raw_ostream &OS) const; 984 void dump() const; 985 986 private: 987 TreePatternNodePtr ParseTreePattern(Init *DI, StringRef OpName); 988 void ComputeNamedNodes(); 989 void ComputeNamedNodes(TreePatternNode *N); 990 }; 991 992 993 inline bool TreePatternNode::UpdateNodeType(unsigned ResNo, 994 const TypeSetByHwMode &InTy, 995 TreePattern &TP) { 996 TypeSetByHwMode VTS(InTy); 997 TP.getInfer().expandOverloads(VTS); 998 return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS); 999 } 1000 1001 inline bool TreePatternNode::UpdateNodeType(unsigned ResNo, 1002 MVT::SimpleValueType InTy, 1003 TreePattern &TP) { 1004 TypeSetByHwMode VTS(InTy); 1005 TP.getInfer().expandOverloads(VTS); 1006 return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS); 1007 } 1008 1009 inline bool TreePatternNode::UpdateNodeType(unsigned ResNo, 1010 ValueTypeByHwMode InTy, 1011 TreePattern &TP) { 1012 TypeSetByHwMode VTS(InTy); 1013 TP.getInfer().expandOverloads(VTS); 1014 return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS); 1015 } 1016 1017 1018 /// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps 1019 /// that has a set ExecuteAlways / DefaultOps field. 1020 struct DAGDefaultOperand { 1021 std::vector<TreePatternNodePtr> DefaultOps; 1022 }; 1023 1024 class DAGInstruction { 1025 std::vector<Record*> Results; 1026 std::vector<Record*> Operands; 1027 std::vector<Record*> ImpResults; 1028 TreePatternNodePtr SrcPattern; 1029 TreePatternNodePtr ResultPattern; 1030 1031 public: 1032 DAGInstruction(std::vector<Record *> &&results, 1033 std::vector<Record *> &&operands, 1034 std::vector<Record *> &&impresults, 1035 TreePatternNodePtr srcpattern = nullptr, 1036 TreePatternNodePtr resultpattern = nullptr) 1037 : Results(std::move(results)), Operands(std::move(operands)), 1038 ImpResults(std::move(impresults)), SrcPattern(srcpattern), 1039 ResultPattern(resultpattern) {} 1040 1041 unsigned getNumResults() const { return Results.size(); } 1042 unsigned getNumOperands() const { return Operands.size(); } 1043 unsigned getNumImpResults() const { return ImpResults.size(); } 1044 const std::vector<Record*>& getImpResults() const { return ImpResults; } 1045 1046 Record *getResult(unsigned RN) const { 1047 assert(RN < Results.size()); 1048 return Results[RN]; 1049 } 1050 1051 Record *getOperand(unsigned ON) const { 1052 assert(ON < Operands.size()); 1053 return Operands[ON]; 1054 } 1055 1056 Record *getImpResult(unsigned RN) const { 1057 assert(RN < ImpResults.size()); 1058 return ImpResults[RN]; 1059 } 1060 1061 TreePatternNodePtr getSrcPattern() const { return SrcPattern; } 1062 TreePatternNodePtr getResultPattern() const { return ResultPattern; } 1063 }; 1064 1065 /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns 1066 /// processed to produce isel. 1067 class PatternToMatch { 1068 Record *SrcRecord; // Originating Record for the pattern. 1069 ListInit *Predicates; // Top level predicate conditions to match. 1070 TreePatternNodePtr SrcPattern; // Source pattern to match. 1071 TreePatternNodePtr DstPattern; // Resulting pattern. 1072 std::vector<Record*> Dstregs; // Physical register defs being matched. 1073 std::string HwModeFeatures; 1074 int AddedComplexity; // Add to matching pattern complexity. 1075 unsigned ID; // Unique ID for the record. 1076 1077 public: 1078 PatternToMatch(Record *srcrecord, ListInit *preds, TreePatternNodePtr src, 1079 TreePatternNodePtr dst, std::vector<Record *> dstregs, 1080 int complexity, unsigned uid, 1081 const Twine &hwmodefeatures = "") 1082 : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src), 1083 DstPattern(dst), Dstregs(std::move(dstregs)), 1084 HwModeFeatures(hwmodefeatures.str()), AddedComplexity(complexity), 1085 ID(uid) {} 1086 1087 Record *getSrcRecord() const { return SrcRecord; } 1088 ListInit *getPredicates() const { return Predicates; } 1089 TreePatternNode *getSrcPattern() const { return SrcPattern.get(); } 1090 TreePatternNodePtr getSrcPatternShared() const { return SrcPattern; } 1091 TreePatternNode *getDstPattern() const { return DstPattern.get(); } 1092 TreePatternNodePtr getDstPatternShared() const { return DstPattern; } 1093 const std::vector<Record*> &getDstRegs() const { return Dstregs; } 1094 StringRef getHwModeFeatures() const { return HwModeFeatures; } 1095 int getAddedComplexity() const { return AddedComplexity; } 1096 unsigned getID() const { return ID; } 1097 1098 std::string getPredicateCheck() const; 1099 void getPredicateRecords(SmallVectorImpl<Record *> &PredicateRecs) const; 1100 1101 /// Compute the complexity metric for the input pattern. This roughly 1102 /// corresponds to the number of nodes that are covered. 1103 int getPatternComplexity(const CodeGenDAGPatterns &CGP) const; 1104 }; 1105 1106 class CodeGenDAGPatterns { 1107 RecordKeeper &Records; 1108 CodeGenTarget Target; 1109 CodeGenIntrinsicTable Intrinsics; 1110 1111 std::map<Record*, SDNodeInfo, LessRecordByID> SDNodes; 1112 std::map<Record*, std::pair<Record*, std::string>, LessRecordByID> 1113 SDNodeXForms; 1114 std::map<Record*, ComplexPattern, LessRecordByID> ComplexPatterns; 1115 std::map<Record *, std::unique_ptr<TreePattern>, LessRecordByID> 1116 PatternFragments; 1117 std::map<Record*, DAGDefaultOperand, LessRecordByID> DefaultOperands; 1118 std::map<Record*, DAGInstruction, LessRecordByID> Instructions; 1119 1120 // Specific SDNode definitions: 1121 Record *intrinsic_void_sdnode; 1122 Record *intrinsic_w_chain_sdnode, *intrinsic_wo_chain_sdnode; 1123 1124 /// PatternsToMatch - All of the things we are matching on the DAG. The first 1125 /// value is the pattern to match, the second pattern is the result to 1126 /// emit. 1127 std::vector<PatternToMatch> PatternsToMatch; 1128 1129 TypeSetByHwMode LegalVTS; 1130 1131 using PatternRewriterFn = std::function<void (TreePattern *)>; 1132 PatternRewriterFn PatternRewriter; 1133 1134 unsigned NumScopes = 0; 1135 1136 public: 1137 CodeGenDAGPatterns(RecordKeeper &R, 1138 PatternRewriterFn PatternRewriter = nullptr); 1139 1140 CodeGenTarget &getTargetInfo() { return Target; } 1141 const CodeGenTarget &getTargetInfo() const { return Target; } 1142 const TypeSetByHwMode &getLegalTypes() const { return LegalVTS; } 1143 1144 Record *getSDNodeNamed(StringRef Name) const; 1145 1146 const SDNodeInfo &getSDNodeInfo(Record *R) const { 1147 auto F = SDNodes.find(R); 1148 assert(F != SDNodes.end() && "Unknown node!"); 1149 return F->second; 1150 } 1151 1152 // Node transformation lookups. 1153 typedef std::pair<Record*, std::string> NodeXForm; 1154 const NodeXForm &getSDNodeTransform(Record *R) const { 1155 auto F = SDNodeXForms.find(R); 1156 assert(F != SDNodeXForms.end() && "Invalid transform!"); 1157 return F->second; 1158 } 1159 1160 const ComplexPattern &getComplexPattern(Record *R) const { 1161 auto F = ComplexPatterns.find(R); 1162 assert(F != ComplexPatterns.end() && "Unknown addressing mode!"); 1163 return F->second; 1164 } 1165 1166 const CodeGenIntrinsic &getIntrinsic(Record *R) const { 1167 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 1168 if (Intrinsics[i].TheDef == R) return Intrinsics[i]; 1169 llvm_unreachable("Unknown intrinsic!"); 1170 } 1171 1172 const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const { 1173 if (IID-1 < Intrinsics.size()) 1174 return Intrinsics[IID-1]; 1175 llvm_unreachable("Bad intrinsic ID!"); 1176 } 1177 1178 unsigned getIntrinsicID(Record *R) const { 1179 for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i) 1180 if (Intrinsics[i].TheDef == R) return i; 1181 llvm_unreachable("Unknown intrinsic!"); 1182 } 1183 1184 const DAGDefaultOperand &getDefaultOperand(Record *R) const { 1185 auto F = DefaultOperands.find(R); 1186 assert(F != DefaultOperands.end() &&"Isn't an analyzed default operand!"); 1187 return F->second; 1188 } 1189 1190 // Pattern Fragment information. 1191 TreePattern *getPatternFragment(Record *R) const { 1192 auto F = PatternFragments.find(R); 1193 assert(F != PatternFragments.end() && "Invalid pattern fragment request!"); 1194 return F->second.get(); 1195 } 1196 TreePattern *getPatternFragmentIfRead(Record *R) const { 1197 auto F = PatternFragments.find(R); 1198 if (F == PatternFragments.end()) 1199 return nullptr; 1200 return F->second.get(); 1201 } 1202 1203 typedef std::map<Record *, std::unique_ptr<TreePattern>, 1204 LessRecordByID>::const_iterator pf_iterator; 1205 pf_iterator pf_begin() const { return PatternFragments.begin(); } 1206 pf_iterator pf_end() const { return PatternFragments.end(); } 1207 iterator_range<pf_iterator> ptfs() const { return PatternFragments; } 1208 1209 // Patterns to match information. 1210 typedef std::vector<PatternToMatch>::const_iterator ptm_iterator; 1211 ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } 1212 ptm_iterator ptm_end() const { return PatternsToMatch.end(); } 1213 iterator_range<ptm_iterator> ptms() const { return PatternsToMatch; } 1214 1215 /// Parse the Pattern for an instruction, and insert the result in DAGInsts. 1216 typedef std::map<Record*, DAGInstruction, LessRecordByID> DAGInstMap; 1217 void parseInstructionPattern( 1218 CodeGenInstruction &CGI, ListInit *Pattern, 1219 DAGInstMap &DAGInsts); 1220 1221 const DAGInstruction &getInstruction(Record *R) const { 1222 auto F = Instructions.find(R); 1223 assert(F != Instructions.end() && "Unknown instruction!"); 1224 return F->second; 1225 } 1226 1227 Record *get_intrinsic_void_sdnode() const { 1228 return intrinsic_void_sdnode; 1229 } 1230 Record *get_intrinsic_w_chain_sdnode() const { 1231 return intrinsic_w_chain_sdnode; 1232 } 1233 Record *get_intrinsic_wo_chain_sdnode() const { 1234 return intrinsic_wo_chain_sdnode; 1235 } 1236 1237 unsigned allocateScope() { return ++NumScopes; } 1238 1239 bool operandHasDefault(Record *Op) const { 1240 return Op->isSubClassOf("OperandWithDefaultOps") && 1241 !getDefaultOperand(Op).DefaultOps.empty(); 1242 } 1243 1244 private: 1245 void ParseNodeInfo(); 1246 void ParseNodeTransforms(); 1247 void ParseComplexPatterns(); 1248 void ParsePatternFragments(bool OutFrags = false); 1249 void ParseDefaultOperands(); 1250 void ParseInstructions(); 1251 void ParsePatterns(); 1252 void ExpandHwModeBasedTypes(); 1253 void InferInstructionFlags(); 1254 void GenerateVariants(); 1255 void VerifyInstructionFlags(); 1256 1257 void ParseOnePattern(Record *TheDef, 1258 TreePattern &Pattern, TreePattern &Result, 1259 const std::vector<Record *> &InstImpResults); 1260 void AddPatternToMatch(TreePattern *Pattern, PatternToMatch &&PTM); 1261 void FindPatternInputsAndOutputs( 1262 TreePattern &I, TreePatternNodePtr Pat, 1263 std::map<std::string, TreePatternNodePtr> &InstInputs, 1264 MapVector<std::string, TreePatternNodePtr, 1265 std::map<std::string, unsigned>> &InstResults, 1266 std::vector<Record *> &InstImpResults); 1267 }; 1268 1269 1270 inline bool SDNodeInfo::ApplyTypeConstraints(TreePatternNode *N, 1271 TreePattern &TP) const { 1272 bool MadeChange = false; 1273 for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i) 1274 MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP); 1275 return MadeChange; 1276 } 1277 1278 } // end namespace llvm 1279 1280 #endif 1281