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