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