llvm/utils/TableGen/CodeGenDAGPatterns.h

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