vendor/llvm/llvm-trunk-r321017

1 files changed, 535 insertions, 192 deletions

diff --git a/utils/TableGen/CodeGenDAGPatterns.h b/utils/TableGen/CodeGenDAGPatterns.h
index 8b3e19142370..afbcb10a4b66 100644
--- a/utils/TableGen/CodeGenDAGPatterns.h
+++ b/utils/TableGen/CodeGenDAGPatterns.h
@@ -15,163 +15,334 @@
 #ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
 #define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
 
+#include "CodeGenHwModes.h"
 #include "CodeGenIntrinsics.h"
 #include "CodeGenTarget.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/MathExtras.h"
 #include <algorithm>
+#include <array>
+#include <functional>
 #include <map>
 #include <set>
 #include <vector>
 
 namespace llvm {
-  class Record;
-  class Init;
-  class ListInit;
-  class DagInit;
-  class SDNodeInfo;
-  class TreePattern;
-  class TreePatternNode;
-  class CodeGenDAGPatterns;
-  class ComplexPattern;
-
-/// EEVT::DAGISelGenValueType - These are some extended forms of
-/// MVT::SimpleValueType that we use as lattice values during type inference.
-/// The existing MVT iAny, fAny and vAny types suffice to represent
-/// arbitrary integer, floating-point, and vector types, so only an unknown
-/// value is needed.
-namespace EEVT {
-  /// TypeSet - This is either empty if it's completely unknown, or holds a set
-  /// of types.  It is used during type inference because register classes can
-  /// have multiple possible types and we don't know which one they get until
-  /// type inference is complete.
-  ///
-  /// TypeSet can have three states:
-  ///    Vector is empty: The type is completely unknown, it can be any valid
-  ///       target type.
-  ///    Vector has multiple constrained types: (e.g. v4i32 + v4f32) it is one
-  ///       of those types only.
-  ///    Vector has one concrete type: The type is completely known.
-  ///
-  class TypeSet {
-    SmallVector<MVT::SimpleValueType, 4> TypeVec;
-  public:
-    TypeSet() {}
-    TypeSet(MVT::SimpleValueType VT, TreePattern &TP);
-    TypeSet(ArrayRef<MVT::SimpleValueType> VTList);
-
-    bool isCompletelyUnknown() const { return TypeVec.empty(); }
-
-    bool isConcrete() const {
-      if (TypeVec.size() != 1) return false;
-      unsigned char T = TypeVec[0]; (void)T;
-      assert(T < MVT::LAST_VALUETYPE || T == MVT::iPTR || T == MVT::iPTRAny);
-      return true;
-    }
 
-    MVT::SimpleValueType getConcrete() const {
-      assert(isConcrete() && "Type isn't concrete yet");
-      return (MVT::SimpleValueType)TypeVec[0];
-    }
+class Record;
+class Init;
+class ListInit;
+class DagInit;
+class SDNodeInfo;
+class TreePattern;
+class TreePatternNode;
+class CodeGenDAGPatterns;
+class ComplexPattern;
+
+/// This represents a set of MVTs. Since the underlying type for the MVT
+/// is uint8_t, there are at most 256 values. To reduce the number of memory
+/// allocations and deallocations, represent the set as a sequence of bits.
+/// To reduce the allocations even further, make MachineValueTypeSet own
+/// the storage and use std::array as the bit container.
+struct MachineValueTypeSet {
+  static_assert(std::is_same<std::underlying_type<MVT::SimpleValueType>::type,
+                             uint8_t>::value,
+                "Change uint8_t here to the SimpleValueType's type");
+  static unsigned constexpr Capacity = std::numeric_limits<uint8_t>::max()+1;
+  using WordType = uint64_t;
+  static unsigned constexpr WordWidth = CHAR_BIT*sizeof(WordType);
+  static unsigned constexpr NumWords = Capacity/WordWidth;
+  static_assert(NumWords*WordWidth == Capacity,
+                "Capacity should be a multiple of WordWidth");
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  MachineValueTypeSet() {
+    clear();
+  }
+
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  unsigned size() const {
+    unsigned Count = 0;
+    for (WordType W : Words)
+      Count += countPopulation(W);
+    return Count;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  void clear() {
+    std::memset(Words.data(), 0, NumWords*sizeof(WordType));
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool empty() const {
+    for (WordType W : Words)
+      if (W != 0)
+        return false;
+    return true;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  unsigned count(MVT T) const {
+    return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1;
+  }
+  std::pair<MachineValueTypeSet&,bool> insert(MVT T) {
+    bool V = count(T.SimpleTy);
+    Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth);
+    return {*this, V};
+  }
+  MachineValueTypeSet &insert(const MachineValueTypeSet &S) {
+    for (unsigned i = 0; i != NumWords; ++i)
+      Words[i] |= S.Words[i];
+    return *this;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  void erase(MVT T) {
+    Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth));
+  }
 
-    bool isDynamicallyResolved() const {
-      return getConcrete() == MVT::iPTR || getConcrete() == MVT::iPTRAny;
+  struct const_iterator {
+    // Some implementations of the C++ library require these traits to be
+    // defined.
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = MVT;
+    using difference_type = ptrdiff_t;
+    using pointer = const MVT*;
+    using reference = const MVT&;
+
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    MVT operator*() const {
+      assert(Pos != Capacity);
+      return MVT::SimpleValueType(Pos);
+    }
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) {
+      Pos = End ? Capacity : find_from_pos(0);
+    }
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    const_iterator &operator++() {
+      assert(Pos != Capacity);
+      Pos = find_from_pos(Pos+1);
+      return *this;
     }
 
-    const SmallVectorImpl<MVT::SimpleValueType> &getTypeList() const {
-      assert(!TypeVec.empty() && "Not a type list!");
-      return TypeVec;
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool operator==(const const_iterator &It) const {
+      return Set == It.Set && Pos == It.Pos;
+    }
+    LLVM_ATTRIBUTE_ALWAYS_INLINE
+    bool operator!=(const const_iterator &It) const {
+      return !operator==(It);
     }
 
-    bool isVoid() const {
-      return TypeVec.size() == 1 && TypeVec[0] == MVT::isVoid;
+  private:
+    unsigned find_from_pos(unsigned P) const {
+      unsigned SkipWords = P / WordWidth;
+      unsigned SkipBits = P % WordWidth;
+      unsigned Count = SkipWords * WordWidth;
+
+      // If P is in the middle of a word, process it manually here, because
+      // the trailing bits need to be masked off to use findFirstSet.
+      if (SkipBits != 0) {
+        WordType W = Set->Words[SkipWords];
+        W &= maskLeadingOnes<WordType>(WordWidth-SkipBits);
+        if (W != 0)
+          return Count + findFirstSet(W);
+        Count += WordWidth;
+        SkipWords++;
+      }
+
+      for (unsigned i = SkipWords; i != NumWords; ++i) {
+        WordType W = Set->Words[i];
+        if (W != 0)
+          return Count + findFirstSet(W);
+        Count += WordWidth;
+      }
+      return Capacity;
     }
 
-    /// hasIntegerTypes - Return true if this TypeSet contains any integer value
-    /// types.
-    bool hasIntegerTypes() const;
+    const MachineValueTypeSet *Set;
+    unsigned Pos;
+  };
 
-    /// hasFloatingPointTypes - Return true if this TypeSet contains an fAny or
-    /// a floating point value type.
-    bool hasFloatingPointTypes() const;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  const_iterator begin() const { return const_iterator(this, false); }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  const_iterator end()   const { return const_iterator(this, true); }
 
-    /// hasScalarTypes - Return true if this TypeSet contains a scalar value
-    /// type.
-    bool hasScalarTypes() const;
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool operator==(const MachineValueTypeSet &S) const {
+    return Words == S.Words;
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool operator!=(const MachineValueTypeSet &S) const {
+    return !operator==(S);
+  }
 
-    /// hasVectorTypes - Return true if this TypeSet contains a vector value
-    /// type.
-    bool hasVectorTypes() const;
+private:
+  friend struct const_iterator;
+  std::array<WordType,NumWords> Words;
+};
 
-    /// getName() - Return this TypeSet as a string.
-    std::string getName() const;
+struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
+  using SetType = MachineValueTypeSet;
+
+  TypeSetByHwMode() = default;
+  TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
+  TypeSetByHwMode(MVT::SimpleValueType VT)
+    : TypeSetByHwMode(ValueTypeByHwMode(VT)) {}
+  TypeSetByHwMode(ValueTypeByHwMode VT)
+    : TypeSetByHwMode(ArrayRef<ValueTypeByHwMode>(&VT, 1)) {}
+  TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList);
+
+  SetType &getOrCreate(unsigned Mode) {
+    if (hasMode(Mode))
+      return get(Mode);
+    return Map.insert({Mode,SetType()}).first->second;
+  }
 
-    /// MergeInTypeInfo - This merges in type information from the specified
-    /// argument.  If 'this' changes, it returns true.  If the two types are
-    /// contradictory (e.g. merge f32 into i32) then this flags an error.
-    bool MergeInTypeInfo(const EEVT::TypeSet &InVT, TreePattern &TP);
+  bool isValueTypeByHwMode(bool AllowEmpty) const;
+  ValueTypeByHwMode getValueTypeByHwMode() const;
 
-    bool MergeInTypeInfo(MVT::SimpleValueType InVT, TreePattern &TP) {
-      return MergeInTypeInfo(EEVT::TypeSet(InVT, TP), TP);
-    }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool isMachineValueType() const {
+    return isDefaultOnly() && Map.begin()->second.size() == 1;
+  }
 
-    /// Force this type list to only contain integer types.
-    bool EnforceInteger(TreePattern &TP);
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  MVT getMachineValueType() const {
+    assert(isMachineValueType());
+    return *Map.begin()->second.begin();
+  }
 
-    /// Force this type list to only contain floating point types.
-    bool EnforceFloatingPoint(TreePattern &TP);
+  bool isPossible() const;
 
-    /// EnforceScalar - Remove all vector types from this type list.
-    bool EnforceScalar(TreePattern &TP);
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  bool isDefaultOnly() const {
+    return Map.size() == 1 && Map.begin()->first == DefaultMode;
+  }
 
-    /// EnforceVector - Remove all non-vector types from this type list.
-    bool EnforceVector(TreePattern &TP);
+  bool insert(const ValueTypeByHwMode &VVT);
+  bool constrain(const TypeSetByHwMode &VTS);
+  template <typename Predicate> bool constrain(Predicate P);
+  template <typename Predicate>
+  bool assign_if(const TypeSetByHwMode &VTS, Predicate P);
 
-    /// EnforceSmallerThan - 'this' must be a smaller VT than Other.  Update
-    /// this an other based on this information.
-    bool EnforceSmallerThan(EEVT::TypeSet &Other, TreePattern &TP);
+  void writeToStream(raw_ostream &OS) const;
+  static void writeToStream(const SetType &S, raw_ostream &OS);
 
-    /// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type
-    /// whose element is VT.
-    bool EnforceVectorEltTypeIs(EEVT::TypeSet &VT, TreePattern &TP);
+  bool operator==(const TypeSetByHwMode &VTS) const;
+  bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); }
 
-    /// EnforceVectorEltTypeIs - 'this' is now constrained to be a vector type
-    /// whose element is VT.
-    bool EnforceVectorEltTypeIs(MVT::SimpleValueType VT, TreePattern &TP);
+  void dump() const;
+  void validate() const;
 
-    /// EnforceVectorSubVectorTypeIs - 'this' is now constrained to
-    /// be a vector type VT.
-    bool EnforceVectorSubVectorTypeIs(EEVT::TypeSet &VT, TreePattern &TP);
+private:
+  /// Intersect two sets. Return true if anything has changed.
+  bool intersect(SetType &Out, const SetType &In);
+};
 
-    /// EnforceSameNumElts - If VTOperand is a scalar, then 'this' is a scalar.
-    /// If VTOperand is a vector, then 'this' must have the same number of
-    /// elements.
-    bool EnforceSameNumElts(EEVT::TypeSet &VT, TreePattern &TP);
+raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T);
 
-    /// EnforceSameSize - 'this' is now constrained to be the same size as VT.
-    bool EnforceSameSize(EEVT::TypeSet &VT, TreePattern &TP);
+struct TypeInfer {
+  TypeInfer(TreePattern &T) : TP(T), ForceMode(0) {}
 
-    bool operator!=(const TypeSet &RHS) const { return TypeVec != RHS.TypeVec; }
-    bool operator==(const TypeSet &RHS) const { return TypeVec == RHS.TypeVec; }
+  bool isConcrete(const TypeSetByHwMode &VTS, bool AllowEmpty) const {
+    return VTS.isValueTypeByHwMode(AllowEmpty);
+  }
+  ValueTypeByHwMode getConcrete(const TypeSetByHwMode &VTS,
+                                bool AllowEmpty) const {
+    assert(VTS.isValueTypeByHwMode(AllowEmpty));
+    return VTS.getValueTypeByHwMode();
+  }
 
-  private:
-    /// FillWithPossibleTypes - Set to all legal types and return true, only
-    /// valid on completely unknown type sets.  If Pred is non-null, only MVTs
-    /// that pass the predicate are added.
-    bool FillWithPossibleTypes(TreePattern &TP,
-                               bool (*Pred)(MVT::SimpleValueType) = nullptr,
-                               const char *PredicateName = nullptr);
+  /// The protocol in the following functions (Merge*, force*, Enforce*,
+  /// expand*) is to return "true" if a change has been made, "false"
+  /// otherwise.
+
+  bool MergeInTypeInfo(TypeSetByHwMode &Out, const TypeSetByHwMode &In);
+  bool MergeInTypeInfo(TypeSetByHwMode &Out, MVT::SimpleValueType InVT) {
+    return MergeInTypeInfo(Out, TypeSetByHwMode(InVT));
+  }
+  bool MergeInTypeInfo(TypeSetByHwMode &Out, ValueTypeByHwMode InVT) {
+    return MergeInTypeInfo(Out, TypeSetByHwMode(InVT));
+  }
+
+  /// Reduce the set \p Out to have at most one element for each mode.
+  bool forceArbitrary(TypeSetByHwMode &Out);
+
+  /// The following four functions ensure that upon return the set \p Out
+  /// will only contain types of the specified kind: integer, floating-point,
+  /// scalar, or vector.
+  /// If \p Out is empty, all legal types of the specified kind will be added
+  /// to it. Otherwise, all types that are not of the specified kind will be
+  /// removed from \p Out.
+  bool EnforceInteger(TypeSetByHwMode &Out);
+  bool EnforceFloatingPoint(TypeSetByHwMode &Out);
+  bool EnforceScalar(TypeSetByHwMode &Out);
+  bool EnforceVector(TypeSetByHwMode &Out);
+
+  /// If \p Out is empty, fill it with all legal types. Otherwise, leave it
+  /// unchanged.
+  bool EnforceAny(TypeSetByHwMode &Out);
+  /// Make sure that for each type in \p Small, there exists a larger type
+  /// in \p Big.
+  bool EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big);
+  /// 1. Ensure that for each type T in \p Vec, T is a vector type, and that
+  ///    for each type U in \p Elem, U is a scalar type.
+  /// 2. Ensure that for each (scalar) type U in \p Elem, there exists a
+  ///    (vector) type T in \p Vec, such that U is the element type of T.
+  bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, TypeSetByHwMode &Elem);
+  bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
+                              const ValueTypeByHwMode &VVT);
+  /// Ensure that for each type T in \p Sub, T is a vector type, and there
+  /// exists a type U in \p Vec such that U is a vector type with the same
+  /// element type as T and at least as many elements as T.
+  bool EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
+                                    TypeSetByHwMode &Sub);
+  /// 1. Ensure that \p V has a scalar type iff \p W has a scalar type.
+  /// 2. Ensure that for each vector type T in \p V, there exists a vector
+  ///    type U in \p W, such that T and U have the same number of elements.
+  /// 3. Ensure that for each vector type U in \p W, there exists a vector
+  ///    type T in \p V, such that T and U have the same number of elements
+  ///    (reverse of 2).
+  bool EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W);
+  /// 1. Ensure that for each type T in \p A, there exists a type U in \p B,
+  ///    such that T and U have equal size in bits.
+  /// 2. Ensure that for each type U in \p B, there exists a type T in \p A
+  ///    such that T and U have equal size in bits (reverse of 1).
+  bool EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B);
+
+  /// For each overloaded type (i.e. of form *Any), replace it with the
+  /// corresponding subset of legal, specific types.
+  void expandOverloads(TypeSetByHwMode &VTS);
+  void expandOverloads(TypeSetByHwMode::SetType &Out,
+                       const TypeSetByHwMode::SetType &Legal);
+
+  struct ValidateOnExit {
+    ValidateOnExit(TypeSetByHwMode &T) : VTS(T) {}
+    ~ValidateOnExit() { VTS.validate(); }
+    TypeSetByHwMode &VTS;
   };
-}
+
+  TreePattern &TP;
+  unsigned ForceMode;     // Mode to use when set.
+  bool CodeGen = false;   // Set during generation of matcher code.
+
+private:
+  TypeSetByHwMode getLegalTypes();
+
+  /// Cached legal types.
+  bool LegalTypesCached = false;
+  TypeSetByHwMode::SetType LegalCache = {};
+};
 
 /// Set type used to track multiply used variables in patterns
-typedef std::set<std::string> MultipleUseVarSet;
+typedef StringSet<> MultipleUseVarSet;
 
 /// SDTypeConstraint - This is a discriminated union of constraints,
 /// corresponding to the SDTypeConstraint tablegen class in Target.td.
 struct SDTypeConstraint {
-  SDTypeConstraint(Record *R);
+  SDTypeConstraint(Record *R, const CodeGenHwModes &CGH);
 
   unsigned OperandNo;   // The operand # this constraint applies to.
   enum {
@@ -182,9 +353,6 @@ struct SDTypeConstraint {
 
   union {   // The discriminated union.
     struct {
-      MVT::SimpleValueType VT;
-    } SDTCisVT_Info;
-    struct {
       unsigned OtherOperandNum;
     } SDTCisSameAs_Info;
     struct {
@@ -200,9 +368,6 @@ struct SDTypeConstraint {
       unsigned OtherOperandNum;
     } SDTCisSubVecOfVec_Info;
     struct {
-      MVT::SimpleValueType VT;
-    } SDTCVecEltisVT_Info;
-    struct {
       unsigned OtherOperandNum;
     } SDTCisSameNumEltsAs_Info;
     struct {
@@ -210,6 +375,10 @@ struct SDTypeConstraint {
     } SDTCisSameSizeAs_Info;
   } x;
 
+  // The VT for SDTCisVT and SDTCVecEltisVT.
+  // Must not be in the union because it has a non-trivial destructor.
+  ValueTypeByHwMode VVT;
+
   /// ApplyTypeConstraint - Given a node in a pattern, apply this type
   /// constraint to the nodes operands.  This returns true if it makes a
   /// change, false otherwise.  If a type contradiction is found, an error
@@ -230,7 +399,8 @@ class SDNodeInfo {
   int NumOperands;
   std::vector<SDTypeConstraint> TypeConstraints;
 public:
-  SDNodeInfo(Record *R);  // Parse the specified record.
+  // Parse the specified record.
+  SDNodeInfo(Record *R, const CodeGenHwModes &CGH);
 
   unsigned getNumResults() const { return NumResults; }
 
@@ -258,14 +428,9 @@ public:
   /// constraints for this node to the operands of the node.  This returns
   /// true if it makes a change, false otherwise.  If a type contradiction is
   /// found, an error is flagged.
-  bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const {
-    bool MadeChange = false;
-    for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i)
-      MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP);
-    return MadeChange;
-  }
+  bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const;
 };
-  
+
 /// TreePredicateFn - This is an abstraction that represents the predicates on
 /// a PatFrag node.  This is a simple one-word wrapper around a pointer to
 /// provide nice accessors.
@@ -277,14 +442,14 @@ public:
   /// TreePredicateFn constructor.  Here 'N' is a subclass of PatFrag.
   TreePredicateFn(TreePattern *N);
 
-  
+
   TreePattern *getOrigPatFragRecord() const { return PatFragRec; }
-  
+
   /// isAlwaysTrue - Return true if this is a noop predicate.
   bool isAlwaysTrue() const;
-  
-  bool isImmediatePattern() const { return !getImmCode().empty(); }
-  
+
+  bool isImmediatePattern() const { return hasImmCode(); }
+
   /// getImmediatePredicateCode - Return the code that evaluates this pattern if
   /// this is an immediate predicate.  It is an error to call this on a
   /// non-immediate pattern.
@@ -293,8 +458,7 @@ public:
     assert(!Result.empty() && "Isn't an immediate pattern!");
     return Result;
   }
-  
-  
+
   bool operator==(const TreePredicateFn &RHS) const {
     return PatFragRec == RHS.PatFragRec;
   }
@@ -304,18 +468,83 @@ public:
   /// Return the name to use in the generated code to reference this, this is
   /// "Predicate_foo" if from a pattern fragment "foo".
   std::string getFnName() const;
-  
+
   /// getCodeToRunOnSDNode - Return the code for the function body that
   /// evaluates this predicate.  The argument is expected to be in "Node",
   /// not N.  This handles casting and conversion to a concrete node type as
   /// appropriate.
   std::string getCodeToRunOnSDNode() const;
-  
+
+  /// Get the data type of the argument to getImmediatePredicateCode().
+  StringRef getImmType() const;
+
+  /// Get a string that describes the type returned by getImmType() but is
+  /// usable as part of an identifier.
+  StringRef getImmTypeIdentifier() const;
+
+  // Is the desired predefined predicate for a load?
+  bool isLoad() const;
+  // Is the desired predefined predicate for a store?
+  bool isStore() const;
+  // Is the desired predefined predicate for an atomic?
+  bool isAtomic() const;
+
+  /// Is this predicate the predefined unindexed load predicate?
+  /// Is this predicate the predefined unindexed store predicate?
+  bool isUnindexed() const;
+  /// Is this predicate the predefined non-extending load predicate?
+  bool isNonExtLoad() const;
+  /// Is this predicate the predefined any-extend load predicate?
+  bool isAnyExtLoad() const;
+  /// Is this predicate the predefined sign-extend load predicate?
+  bool isSignExtLoad() const;
+  /// Is this predicate the predefined zero-extend load predicate?
+  bool isZeroExtLoad() const;
+  /// Is this predicate the predefined non-truncating store predicate?
+  bool isNonTruncStore() const;
+  /// Is this predicate the predefined truncating store predicate?
+  bool isTruncStore() const;
+
+  /// Is this predicate the predefined monotonic atomic predicate?
+  bool isAtomicOrderingMonotonic() const;
+  /// Is this predicate the predefined acquire atomic predicate?
+  bool isAtomicOrderingAcquire() const;
+  /// Is this predicate the predefined release atomic predicate?
+  bool isAtomicOrderingRelease() const;
+  /// Is this predicate the predefined acquire-release atomic predicate?
+  bool isAtomicOrderingAcquireRelease() const;
+  /// Is this predicate the predefined sequentially consistent atomic predicate?
+  bool isAtomicOrderingSequentiallyConsistent() const;
+
+  /// Is this predicate the predefined acquire-or-stronger atomic predicate?
+  bool isAtomicOrderingAcquireOrStronger() const;
+  /// Is this predicate the predefined weaker-than-acquire atomic predicate?
+  bool isAtomicOrderingWeakerThanAcquire() const;
+
+  /// Is this predicate the predefined release-or-stronger atomic predicate?
+  bool isAtomicOrderingReleaseOrStronger() const;
+  /// Is this predicate the predefined weaker-than-release atomic predicate?
+  bool isAtomicOrderingWeakerThanRelease() const;
+
+  /// If non-null, indicates that this predicate is a predefined memory VT
+  /// predicate for a load/store and returns the ValueType record for the memory VT.
+  Record *getMemoryVT() const;
+  /// If non-null, indicates that this predicate is a predefined memory VT
+  /// predicate (checking only the scalar type) for load/store and returns the
+  /// ValueType record for the memory VT.
+  Record *getScalarMemoryVT() const;
+
 private:
+  bool hasPredCode() const;
+  bool hasImmCode() const;
   std::string getPredCode() const;
   std::string getImmCode() const;
+  bool immCodeUsesAPInt() const;
+  bool immCodeUsesAPFloat() const;
+
+  bool isPredefinedPredicateEqualTo(StringRef Field, bool Value) const;
 };
-  
+
 
 /// FIXME: TreePatternNode's can be shared in some cases (due to dag-shaped
 /// patterns), and as such should be ref counted.  We currently just leak all
@@ -324,7 +553,7 @@ class TreePatternNode {
   /// The type of each node result.  Before and during type inference, each
   /// result may be a set of possible types.  After (successful) type inference,
   /// each is a single concrete type.
-  SmallVector<EEVT::TypeSet, 1> Types;
+  std::vector<TypeSetByHwMode> Types;
 
   /// Operator - The Record for the operator if this is an interior node (not
   /// a leaf).
@@ -367,22 +596,24 @@ public:
 
   // Type accessors.
   unsigned getNumTypes() const { return Types.size(); }
-  MVT::SimpleValueType getType(unsigned ResNo) const {
-    return Types[ResNo].getConcrete();
+  ValueTypeByHwMode getType(unsigned ResNo) const {
+    return Types[ResNo].getValueTypeByHwMode();
   }
-  const SmallVectorImpl<EEVT::TypeSet> &getExtTypes() const { return Types; }
-  const EEVT::TypeSet &getExtType(unsigned ResNo) const { return Types[ResNo]; }
-  EEVT::TypeSet &getExtType(unsigned ResNo) { return Types[ResNo]; }
-  void setType(unsigned ResNo, const EEVT::TypeSet &T) { Types[ResNo] = T; }
-
-  bool hasTypeSet(unsigned ResNo) const {
-    return Types[ResNo].isConcrete();
+  const std::vector<TypeSetByHwMode> &getExtTypes() const { return Types; }
+  const TypeSetByHwMode &getExtType(unsigned ResNo) const {
+    return Types[ResNo];
+  }
+  TypeSetByHwMode &getExtType(unsigned ResNo) { return Types[ResNo]; }
+  void setType(unsigned ResNo, const TypeSetByHwMode &T) { Types[ResNo] = T; }
+  MVT::SimpleValueType getSimpleType(unsigned ResNo) const {
+    return Types[ResNo].getMachineValueType().SimpleTy;
   }
-  bool isTypeCompletelyUnknown(unsigned ResNo) const {
-    return Types[ResNo].isCompletelyUnknown();
+
+  bool hasConcreteType(unsigned ResNo) const {
+    return Types[ResNo].isValueTypeByHwMode(false);
   }
-  bool isTypeDynamicallyResolved(unsigned ResNo) const {
-    return Types[ResNo].isDynamicallyResolved();
+  bool isTypeCompletelyUnknown(unsigned ResNo, TreePattern &TP) const {
+    return Types[ResNo].empty();
   }
 
   Init *getLeafValue() const { assert(isLeaf()); return Val; }
@@ -401,8 +632,12 @@ public:
     return false;
   }
 
+  bool hasProperTypeByHwMode() const;
+  bool hasPossibleType() const;
+  bool setDefaultMode(unsigned Mode);
+
   bool hasAnyPredicate() const { return !PredicateFns.empty(); }
-  
+
   const std::vector<TreePredicateFn> &getPredicateFns() const {
     return PredicateFns;
   }
@@ -484,15 +719,12 @@ public:   // Higher level manipulation routines.
   /// information.  If N already contains a conflicting type, then flag an
   /// error.  This returns true if any information was updated.
   ///
-  bool UpdateNodeType(unsigned ResNo, const EEVT::TypeSet &InTy,
-                      TreePattern &TP) {
-    return Types[ResNo].MergeInTypeInfo(InTy, TP);
-  }
-
+  bool UpdateNodeType(unsigned ResNo, const TypeSetByHwMode &InTy,
+                      TreePattern &TP);
   bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy,
-                      TreePattern &TP) {
-    return Types[ResNo].MergeInTypeInfo(EEVT::TypeSet(InTy, TP), TP);
-  }
+                      TreePattern &TP);
+  bool UpdateNodeType(unsigned ResNo, ValueTypeByHwMode InTy,
+                      TreePattern &TP);
 
   // Update node type with types inferred from an instruction operand or result
   // def from the ins/outs lists.
@@ -501,14 +733,7 @@ public:   // Higher level manipulation routines.
 
   /// ContainsUnresolvedType - Return true if this tree contains any
   /// unresolved types.
-  bool ContainsUnresolvedType() const {
-    for (unsigned i = 0, e = Types.size(); i != e; ++i)
-      if (!Types[i].isConcrete()) return true;
-
-    for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
-      if (getChild(i)->ContainsUnresolvedType()) return true;
-    return false;
-  }
+  bool ContainsUnresolvedType(TreePattern &TP) const;
 
   /// canPatternMatch - If it is impossible for this pattern to match on this
   /// target, fill in Reason and return false.  Otherwise, return true.
@@ -560,6 +785,9 @@ class TreePattern {
   /// number for each operand encountered in a ComplexPattern to aid in that
   /// check.
   StringMap<std::pair<Record *, unsigned>> ComplexPatternOperands;
+
+  TypeInfer Infer;
+
 public:
 
   /// TreePattern constructor - Parse the specified DagInits into the
@@ -576,6 +804,7 @@ public:
   const std::vector<TreePatternNode*> &getTrees() const { return Trees; }
   unsigned getNumTrees() const { return Trees.size(); }
   TreePatternNode *getTree(unsigned i) const { return Trees[i]; }
+  void setTree(unsigned i, TreePatternNode *Tree) { Trees[i] = Tree; }
   TreePatternNode *getOnlyTree() const {
     assert(Trees.size() == 1 && "Doesn't have exactly one pattern!");
     return Trees[0];
@@ -625,6 +854,8 @@ public:
     HasError = false;
   }
 
+  TypeInfer &getInfer() { return Infer; }
+
   void print(raw_ostream &OS) const;
   void dump() const;
 
@@ -634,6 +865,32 @@ private:
   void ComputeNamedNodes(TreePatternNode *N);
 };
 
+
+inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
+                                            const TypeSetByHwMode &InTy,
+                                            TreePattern &TP) {
+  TypeSetByHwMode VTS(InTy);
+  TP.getInfer().expandOverloads(VTS);
+  return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
+}
+
+inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
+                                            MVT::SimpleValueType InTy,
+                                            TreePattern &TP) {
+  TypeSetByHwMode VTS(InTy);
+  TP.getInfer().expandOverloads(VTS);
+  return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
+}
+
+inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
+                                            ValueTypeByHwMode InTy,
+                                            TreePattern &TP) {
+  TypeSetByHwMode VTS(InTy);
+  TP.getInfer().expandOverloads(VTS);
+  return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
+}
+
+
 /// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps
 /// that has a set ExecuteAlways / DefaultOps field.
 struct DAGDefaultOperand {
@@ -680,31 +937,89 @@ public:
   TreePatternNode *getResultPattern() const { return ResultPattern; }
 };
 
+/// This class represents a condition that has to be satisfied for a pattern
+/// to be tried. It is a generalization of a class "Pattern" from Target.td:
+/// in addition to the Target.td's predicates, this class can also represent
+/// conditions associated with HW modes. Both types will eventually become
+/// strings containing C++ code to be executed, the difference is in how
+/// these strings are generated.
+class Predicate {
+public:
+  Predicate(Record *R, bool C = true) : Def(R), IfCond(C), IsHwMode(false) {
+    assert(R->isSubClassOf("Predicate") &&
+           "Predicate objects should only be created for records derived"
+           "from Predicate class");
+  }
+  Predicate(StringRef FS, bool C = true) : Def(nullptr), Features(FS.str()),
+    IfCond(C), IsHwMode(true) {}
+
+  /// Return a string which contains the C++ condition code that will serve
+  /// as a predicate during instruction selection.
+  std::string getCondString() const {
+    // The string will excute in a subclass of SelectionDAGISel.
+    // Cast to std::string explicitly to avoid ambiguity with StringRef.
+    std::string C = IsHwMode
+        ? std::string("MF->getSubtarget().checkFeatures(\"" + Features + "\")")
+        : std::string(Def->getValueAsString("CondString"));
+    return IfCond ? C : "!("+C+')';
+  }
+  bool operator==(const Predicate &P) const {
+    return IfCond == P.IfCond && IsHwMode == P.IsHwMode && Def == P.Def;
+  }
+  bool operator<(const Predicate &P) const {
+    if (IsHwMode != P.IsHwMode)
+      return IsHwMode < P.IsHwMode;
+    assert(!Def == !P.Def && "Inconsistency between Def and IsHwMode");
+    if (IfCond != P.IfCond)
+      return IfCond < P.IfCond;
+    if (Def)
+      return LessRecord()(Def, P.Def);
+    return Features < P.Features;
+  }
+  Record *Def;            ///< Predicate definition from .td file, null for
+                          ///< HW modes.
+  std::string Features;   ///< Feature string for HW mode.
+  bool IfCond;            ///< The boolean value that the condition has to
+                          ///< evaluate to for this predicate to be true.
+  bool IsHwMode;          ///< Does this predicate correspond to a HW mode?
+};
+
 /// PatternToMatch - Used by CodeGenDAGPatterns to keep tab of patterns
 /// processed to produce isel.
 class PatternToMatch {
 public:
-  PatternToMatch(Record *srcrecord, ListInit *preds, TreePatternNode *src,
-                 TreePatternNode *dst, std::vector<Record *> dstregs,
-                 int complexity, unsigned uid)
-      : SrcRecord(srcrecord), Predicates(preds), SrcPattern(src),
-        DstPattern(dst), Dstregs(std::move(dstregs)),
-        AddedComplexity(complexity), ID(uid) {}
+  PatternToMatch(Record *srcrecord, const std::vector<Predicate> &preds,
+                 TreePatternNode *src, TreePatternNode *dst,
+                 const std::vector<Record*> &dstregs,
+                 int complexity, unsigned uid, unsigned setmode = 0)
+    : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
+      Predicates(preds), Dstregs(std::move(dstregs)),
+      AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}
+
+  PatternToMatch(Record *srcrecord, std::vector<Predicate> &&preds,
+                 TreePatternNode *src, TreePatternNode *dst,
+                 std::vector<Record*> &&dstregs,
+                 int complexity, unsigned uid, unsigned setmode = 0)
+    : SrcRecord(srcrecord), SrcPattern(src), DstPattern(dst),
+      Predicates(preds), Dstregs(std::move(dstregs)),
+      AddedComplexity(complexity), ID(uid), ForceMode(setmode) {}
 
   Record          *SrcRecord;   // Originating Record for the pattern.
-  ListInit        *Predicates;  // Top level predicate conditions to match.
   TreePatternNode *SrcPattern;  // Source pattern to match.
   TreePatternNode *DstPattern;  // Resulting pattern.
+  std::vector<Predicate> Predicates;  // Top level predicate conditions
+                                      // to match.
   std::vector<Record*> Dstregs; // Physical register defs being matched.
   int              AddedComplexity; // Add to matching pattern complexity.
   unsigned         ID;          // Unique ID for the record.
+  unsigned         ForceMode;   // Force this mode in type inference when set.
 
   Record          *getSrcRecord()  const { return SrcRecord; }
-  ListInit        *getPredicates() const { return Predicates; }
   TreePatternNode *getSrcPattern() const { return SrcPattern; }
   TreePatternNode *getDstPattern() const { return DstPattern; }
   const std::vector<Record*> &getDstRegs() const { return Dstregs; }
   int         getAddedComplexity() const { return AddedComplexity; }
+  const std::vector<Predicate> &getPredicates() const { return Predicates; }
 
   std::string getPredicateCheck() const;
 
@@ -720,7 +1035,8 @@ class CodeGenDAGPatterns {
   CodeGenIntrinsicTable TgtIntrinsics;
 
   std::map<Record*, SDNodeInfo, LessRecordByID> SDNodes;
-  std::map<Record*, std::pair<Record*, std::string>, LessRecordByID> SDNodeXForms;
+  std::map<Record*, std::pair<Record*, std::string>, LessRecordByID>
+      SDNodeXForms;
   std::map<Record*, ComplexPattern, LessRecordByID> ComplexPatterns;
   std::map<Record *, std::unique_ptr<TreePattern>, LessRecordByID>
       PatternFragments;
@@ -735,24 +1051,34 @@ class CodeGenDAGPatterns {
   /// value is the pattern to match, the second pattern is the result to
   /// emit.
   std::vector<PatternToMatch> PatternsToMatch;
+
+  TypeSetByHwMode LegalVTS;
+
+  using PatternRewriterFn = std::function<void (TreePattern *)>;
+  PatternRewriterFn PatternRewriter;
+
 public:
-  CodeGenDAGPatterns(RecordKeeper &R);
+  CodeGenDAGPatterns(RecordKeeper &R,
+                     PatternRewriterFn PatternRewriter = nullptr);
 
   CodeGenTarget &getTargetInfo() { return Target; }
   const CodeGenTarget &getTargetInfo() const { return Target; }
+  const TypeSetByHwMode &getLegalTypes() const { return LegalVTS; }
 
   Record *getSDNodeNamed(const std::string &Name) const;
 
   const SDNodeInfo &getSDNodeInfo(Record *R) const {
-    assert(SDNodes.count(R) && "Unknown node!");
-    return SDNodes.find(R)->second;
+    auto F = SDNodes.find(R);
+    assert(F != SDNodes.end() && "Unknown node!");
+    return F->second;
   }
 
   // Node transformation lookups.
   typedef std::pair<Record*, std::string> NodeXForm;
   const NodeXForm &getSDNodeTransform(Record *R) const {
-    assert(SDNodeXForms.count(R) && "Invalid transform!");
-    return SDNodeXForms.find(R)->second;
+    auto F = SDNodeXForms.find(R);
+    assert(F != SDNodeXForms.end() && "Invalid transform!");
+    return F->second;
   }
 
   typedef std::map<Record*, NodeXForm, LessRecordByID>::const_iterator
@@ -762,8 +1088,9 @@ public:
 
 
   const ComplexPattern &getComplexPattern(Record *R) const {
-    assert(ComplexPatterns.count(R) && "Unknown addressing mode!");
-    return ComplexPatterns.find(R)->second;
+    auto F = ComplexPatterns.find(R);
+    assert(F != ComplexPatterns.end() && "Unknown addressing mode!");
+    return F->second;
   }
 
   const CodeGenIntrinsic &getIntrinsic(Record *R) const {
@@ -791,19 +1118,22 @@ public:
   }
 
   const DAGDefaultOperand &getDefaultOperand(Record *R) const {
-    assert(DefaultOperands.count(R) &&"Isn't an analyzed default operand!");
-    return DefaultOperands.find(R)->second;
+    auto F = DefaultOperands.find(R);
+    assert(F != DefaultOperands.end() &&"Isn't an analyzed default operand!");
+    return F->second;
   }
 
   // Pattern Fragment information.
   TreePattern *getPatternFragment(Record *R) const {
-    assert(PatternFragments.count(R) && "Invalid pattern fragment request!");
-    return PatternFragments.find(R)->second.get();
+    auto F = PatternFragments.find(R);
+    assert(F != PatternFragments.end() && "Invalid pattern fragment request!");
+    return F->second.get();
   }
   TreePattern *getPatternFragmentIfRead(Record *R) const {
-    if (!PatternFragments.count(R))
+    auto F = PatternFragments.find(R);
+    if (F == PatternFragments.end())
       return nullptr;
-    return PatternFragments.find(R)->second.get();
+    return F->second.get();
   }
 
   typedef std::map<Record *, std::unique_ptr<TreePattern>,
@@ -825,8 +1155,9 @@ public:
       DAGInstMap &DAGInsts);
 
   const DAGInstruction &getInstruction(Record *R) const {
-    assert(Instructions.count(R) && "Unknown instruction!");
-    return Instructions.find(R)->second;
+    auto F = Instructions.find(R);
+    assert(F != Instructions.end() && "Unknown instruction!");
+    return F->second;
   }
 
   Record *get_intrinsic_void_sdnode() const {
@@ -849,10 +1180,13 @@ private:
   void ParseDefaultOperands();
   void ParseInstructions();
   void ParsePatterns();
+  void ExpandHwModeBasedTypes();
   void InferInstructionFlags();
   void GenerateVariants();
   void VerifyInstructionFlags();
 
+  std::vector<Predicate> makePredList(ListInit *L);
+
   void AddPatternToMatch(TreePattern *Pattern, PatternToMatch &&PTM);
   void FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat,
                                    std::map<std::string,
@@ -861,6 +1195,15 @@ private:
                                    TreePatternNode*> &InstResults,
                                    std::vector<Record*> &InstImpResults);
 };
+
+
+inline bool SDNodeInfo::ApplyTypeConstraints(TreePatternNode *N,
+                                             TreePattern &TP) const {
+    bool MadeChange = false;
+    for (unsigned i = 0, e = TypeConstraints.size(); i != e; ++i)
+      MadeChange |= TypeConstraints[i].ApplyTypeConstraint(N, *this, TP);
+    return MadeChange;
+  }
 } // end namespace llvm
 
 #endif