contrib/llvm/utils/TableGen/CodeGenDAGPatterns.h

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