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