Reformat.
[oota-llvm.git] / include / llvm / CodeGen / SelectionDAGNodes.h
index a6c72ca2d1c7b1619ce4970d67a57ffa1cb13170..6419fd3c4ec9a04431534d76d8eebfd1a46dc343 100644 (file)
 #ifndef LLVM_CODEGEN_SELECTIONDAGNODES_H
 #define LLVM_CODEGEN_SELECTIONDAGNODES_H
 
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/ValueTypes.h"
@@ -48,9 +50,10 @@ template <typename T> struct DenseMapInfo;
 template <typename T> struct simplify_type;
 template <typename T> struct ilist_traits;
 
-void checkForCycles(const SDNode *N);
+void checkForCycles(const SDNode *N, const SelectionDAG *DAG = nullptr,
+                    bool force = false);
 
-/// SDVTList - This represents a list of ValueType's that has been intern'd by
+/// This represents a list of ValueType's that has been intern'd by
 /// a SelectionDAG.  Instances of this simple value class are returned by
 /// SelectionDAG::getVTList(...).
 ///
@@ -62,11 +65,11 @@ struct SDVTList {
 namespace ISD {
   /// Node predicates
 
-  /// isBuildVectorAllOnes - Return true if the specified node is a
+  /// Return true if the specified node is a
   /// BUILD_VECTOR where all of the elements are ~0 or undef.
   bool isBuildVectorAllOnes(const SDNode *N);
 
-  /// isBuildVectorAllZeros - Return true if the specified node is a
+  /// Return true if the specified node is a
   /// BUILD_VECTOR where all of the elements are 0 or undef.
   bool isBuildVectorAllZeros(const SDNode *N);
 
@@ -74,18 +77,22 @@ namespace ISD {
   /// all ConstantSDNode or undef.
   bool isBuildVectorOfConstantSDNodes(const SDNode *N);
 
-  /// isScalarToVector - Return true if the specified node is a
+  /// \brief Return true if the specified node is a BUILD_VECTOR node of
+  /// all ConstantFPSDNode or undef.
+  bool isBuildVectorOfConstantFPSDNodes(const SDNode *N);
+
+  /// Return true if the specified node is a
   /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
   /// element is not an undef.
   bool isScalarToVector(const SDNode *N);
 
-  /// allOperandsUndef - Return true if the node has at least one operand
+  /// Return true if the node has at least one operand
   /// and all operands of the specified node are ISD::UNDEF.
   bool allOperandsUndef(const SDNode *N);
 }  // end llvm:ISD namespace
 
 //===----------------------------------------------------------------------===//
-/// SDValue - Unlike LLVM values, Selection DAG nodes may return multiple
+/// Unlike LLVM values, Selection DAG nodes may return multiple
 /// values as the result of a computation.  Many nodes return multiple values,
 /// from loads (which define a token and a return value) to ADDC (which returns
 /// a result and a carry value), to calls (which may return an arbitrary number
@@ -96,11 +103,13 @@ namespace ISD {
 /// of information is represented with the SDValue value type.
 ///
 class SDValue {
+  friend struct DenseMapInfo<SDValue>;
+
   SDNode *Node;       // The node defining the value we are using.
   unsigned ResNo;     // Which return value of the node we are using.
 public:
-  SDValue() : Node(0), ResNo(0) {}
-  SDValue(SDNode *node, unsigned resno) : Node(node), ResNo(resno) {}
+  SDValue() : Node(nullptr), ResNo(0) {}
+  SDValue(SDNode *node, unsigned resno);
 
   /// get the index which selects a specific result in the SDNode
   unsigned getResNo() const { return ResNo; }
@@ -122,16 +131,18 @@ public:
   bool operator<(const SDValue &O) const {
     return std::tie(Node, ResNo) < std::tie(O.Node, O.ResNo);
   }
+  explicit operator bool() const {
+    return Node != nullptr;
+  }
 
   SDValue getValue(unsigned R) const {
     return SDValue(Node, R);
   }
 
-  // isOperandOf - Return true if this node is an operand of N.
+  // Return true if this node is an operand of N.
   bool isOperandOf(SDNode *N) const;
 
-  /// getValueType - Return the ValueType of the referenced return value.
-  ///
+  /// Return the ValueType of the referenced return value.
   inline EVT getValueType() const;
 
   /// Return the simple ValueType of the referenced return value.
@@ -139,8 +150,7 @@ public:
     return getValueType().getSimpleVT();
   }
 
-  /// getValueSizeInBits - Returns the size of the value in bits.
-  ///
+  /// Returns the size of the value in bits.
   unsigned getValueSizeInBits() const {
     return getValueType().getSizeInBits();
   }
@@ -158,36 +168,36 @@ public:
   inline bool isTargetOpcode() const;
   inline bool isMachineOpcode() const;
   inline unsigned getMachineOpcode() const;
-  inline const DebugLoc getDebugLoc() const;
+  inline const DebugLoc &getDebugLoc() const;
   inline void dump() const;
   inline void dumpr() const;
 
-  /// reachesChainWithoutSideEffects - Return true if this operand (which must
-  /// be a chain) reaches the specified operand without crossing any
-  /// side-effecting instructions.  In practice, this looks through token
-  /// factors and non-volatile loads.  In order to remain efficient, this only
+  /// Return true if this operand (which must be a chain) reaches the
+  /// specified operand without crossing any side-effecting instructions.
+  /// In practice, this looks through token factors and non-volatile loads.
+  /// In order to remain efficient, this only
   /// looks a couple of nodes in, it does not do an exhaustive search.
   bool reachesChainWithoutSideEffects(SDValue Dest,
                                       unsigned Depth = 2) const;
 
-  /// use_empty - Return true if there are no nodes using value ResNo
-  /// of Node.
-  ///
+  /// Return true if there are no nodes using value ResNo of Node.
   inline bool use_empty() const;
 
-  /// hasOneUse - Return true if there is exactly one node using value
-  /// ResNo of Node.
-  ///
+  /// Return true if there is exactly one node using value ResNo of Node.
   inline bool hasOneUse() const;
 };
 
 
 template<> struct DenseMapInfo<SDValue> {
   static inline SDValue getEmptyKey() {
-    return SDValue((SDNode*)-1, -1U);
+    SDValue V;
+    V.ResNo = -1U;
+    return V;
   }
   static inline SDValue getTombstoneKey() {
-    return SDValue((SDNode*)-1, 0);
+    SDValue V;
+    V.ResNo = -2U;
+    return V;
   }
   static unsigned getHashValue(const SDValue &Val) {
     return ((unsigned)((uintptr_t)Val.getNode() >> 4) ^
@@ -200,7 +210,7 @@ template<> struct DenseMapInfo<SDValue> {
 template <> struct isPodLike<SDValue> { static const bool value = true; };
 
 
-/// simplify_type specializations - Allow casting operators to work directly on
+/// Allow casting operators to work directly on
 /// SDValues as if they were SDNode*'s.
 template<> struct simplify_type<SDValue> {
   typedef SDNode* SimpleType;
@@ -215,7 +225,7 @@ template<> struct simplify_type<const SDValue> {
   }
 };
 
-/// SDUse - Represents a use of a SDNode. This class holds an SDValue,
+/// Represents a use of a SDNode. This class holds an SDValue,
 /// which records the SDNode being used and the result number, a
 /// pointer to the SDNode using the value, and Next and Prev pointers,
 /// which link together all the uses of an SDNode.
@@ -229,11 +239,11 @@ class SDUse {
   /// this operand.
   SDUse **Prev, *Next;
 
-  SDUse(const SDUse &U) LLVM_DELETED_FUNCTION;
-  void operator=(const SDUse &U) LLVM_DELETED_FUNCTION;
+  SDUse(const SDUse &U) = delete;
+  void operator=(const SDUse &U) = delete;
 
 public:
-  SDUse() : Val(), User(NULL), Prev(NULL), Next(NULL) {}
+  SDUse() : Val(), User(nullptr), Prev(nullptr), Next(nullptr) {}
 
   /// Normally SDUse will just implicitly convert to an SDValue that it holds.
   operator const SDValue&() const { return Val; }
@@ -242,30 +252,30 @@ public:
   /// the SDValue.
   const SDValue &get() const { return Val; }
 
-  /// getUser - This returns the SDNode that contains this Use.
+  /// This returns the SDNode that contains this Use.
   SDNode *getUser() { return User; }
 
-  /// getNext - Get the next SDUse in the use list.
+  /// Get the next SDUse in the use list.
   SDUse *getNext() const { return Next; }
 
-  /// getNode - Convenience function for get().getNode().
+  /// Convenience function for get().getNode().
   SDNode *getNode() const { return Val.getNode(); }
-  /// getResNo - Convenience function for get().getResNo().
+  /// Convenience function for get().getResNo().
   unsigned getResNo() const { return Val.getResNo(); }
-  /// getValueType - Convenience function for get().getValueType().
+  /// Convenience function for get().getValueType().
   EVT getValueType() const { return Val.getValueType(); }
 
-  /// operator== - Convenience function for get().operator==
+  /// Convenience function for get().operator==
   bool operator==(const SDValue &V) const {
     return Val == V;
   }
 
-  /// operator!= - Convenience function for get().operator!=
+  /// Convenience function for get().operator!=
   bool operator!=(const SDValue &V) const {
     return Val != V;
   }
 
-  /// operator< - Convenience function for get().operator<
+  /// Convenience function for get().operator<
   bool operator<(const SDValue &V) const {
     return Val < V;
   }
@@ -276,13 +286,13 @@ private:
 
   void setUser(SDNode *p) { User = p; }
 
-  /// set - Remove this use from its existing use list, assign it the
+  /// Remove this use from its existing use list, assign it the
   /// given value, and add it to the new value's node's use list.
   inline void set(const SDValue &V);
-  /// setInitial - like set, but only supports initializing a newly-allocated
+  /// Like set, but only supports initializing a newly-allocated
   /// SDUse with a non-null value.
   inline void setInitial(const SDValue &V);
-  /// setNode - like set, but only sets the Node portion of the value,
+  /// Like set, but only sets the Node portion of the value,
   /// leaving the ResNo portion unmodified.
   inline void setNode(SDNode *N);
 
@@ -309,47 +319,45 @@ template<> struct simplify_type<SDUse> {
 };
 
 
-/// SDNode - Represents one node in the SelectionDAG.
+/// Represents one node in the SelectionDAG.
 ///
 class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
 private:
-  /// NodeType - The operation that this node performs.
-  ///
+  /// The operation that this node performs.
   int16_t NodeType;
 
-  /// OperandsNeedDelete - This is true if OperandList was new[]'d.  If true,
+  /// This is true if OperandList was new[]'d.  If true,
   /// then they will be delete[]'d when the node is destroyed.
   uint16_t OperandsNeedDelete : 1;
 
-  /// HasDebugValue - This tracks whether this node has one or more dbg_value
+  /// This tracks whether this node has one or more dbg_value
   /// nodes corresponding to it.
   uint16_t HasDebugValue : 1;
 
 protected:
-  /// SubclassData - This member is defined by this class, but is not used for
+  /// This member is defined by this class, but is not used for
   /// anything.  Subclasses can use it to hold whatever state they find useful.
   /// This field is initialized to zero by the ctor.
   uint16_t SubclassData : 14;
 
 private:
-  /// NodeId - Unique id per SDNode in the DAG.
+  /// Unique id per SDNode in the DAG.
   int NodeId;
 
-  /// OperandList - The values that are used by this operation.
-  ///
+  /// The values that are used by this operation.
   SDUse *OperandList;
 
-  /// ValueList - The types of the values this node defines.  SDNode's may
+  /// The types of the values this node defines.  SDNode's may
   /// define multiple values simultaneously.
   const EVT *ValueList;
 
-  /// UseList - List of uses for this SDNode.
+  /// List of uses for this SDNode.
   SDUse *UseList;
 
-  /// NumOperands/NumValues - The number of entries in the Operand/Value list.
+  /// The number of entries in the Operand/Value list.
   unsigned short NumOperands, NumValues;
 
-  /// debugLoc - source line information.
+  /// Source line information.
   DebugLoc debugLoc;
 
   // The ordering of the SDNodes. It roughly corresponds to the ordering of the
@@ -359,7 +367,7 @@ private:
   // this ordering.
   unsigned IROrder;
 
-  /// getValueTypeList - Return a pointer to the specified value type.
+  /// Return a pointer to the specified value type.
   static const EVT *getValueTypeList(EVT VT);
 
   friend class SelectionDAG;
@@ -370,28 +378,38 @@ public:
   //  Accessors
   //
 
-  /// getOpcode - Return the SelectionDAG opcode value for this node. For
+  /// Return the SelectionDAG opcode value for this node. For
   /// pre-isel nodes (those for which isMachineOpcode returns false), these
   /// are the opcode values in the ISD and <target>ISD namespaces. For
   /// post-isel opcodes, see getMachineOpcode.
   unsigned getOpcode()  const { return (unsigned short)NodeType; }
 
-  /// isTargetOpcode - Test if this node has a target-specific opcode (in the
+  /// Test if this node has a target-specific opcode (in the
   /// \<target\>ISD namespace).
   bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
 
-  /// isTargetMemoryOpcode - Test if this node has a target-specific
+  /// Test if this node has a target-specific
   /// memory-referencing opcode (in the \<target\>ISD namespace and
   /// greater than FIRST_TARGET_MEMORY_OPCODE).
   bool isTargetMemoryOpcode() const {
     return NodeType >= ISD::FIRST_TARGET_MEMORY_OPCODE;
   }
 
-  /// isMachineOpcode - Test if this node has a post-isel opcode, directly
+  /// Test if this node is a memory intrinsic (with valid pointer information).
+  /// INTRINSIC_W_CHAIN and INTRINSIC_VOID nodes are sometimes created for
+  /// non-memory intrinsics (with chains) that are not really instances of
+  /// MemSDNode. For such nodes, we need some extra state to determine the
+  /// proper classof relationship.
+  bool isMemIntrinsic() const {
+    return (NodeType == ISD::INTRINSIC_W_CHAIN ||
+            NodeType == ISD::INTRINSIC_VOID) && ((SubclassData >> 13) & 1);
+  }
+
+  /// Test if this node has a post-isel opcode, directly
   /// corresponding to a MachineInstr opcode.
   bool isMachineOpcode() const { return NodeType < 0; }
 
-  /// getMachineOpcode - This may only be called if isMachineOpcode returns
+  /// This may only be called if isMachineOpcode returns
   /// true. It returns the MachineInstr opcode value that the node's opcode
   /// corresponds to.
   unsigned getMachineOpcode() const {
@@ -399,50 +417,44 @@ public:
     return ~NodeType;
   }
 
-  /// getHasDebugValue - get this bit.
+  /// Get this bit.
   bool getHasDebugValue() const { return HasDebugValue; }
 
-  /// setHasDebugValue - set this bit.
+  /// Set this bit.
   void setHasDebugValue(bool b) { HasDebugValue = b; }
 
-  /// use_empty - Return true if there are no uses of this node.
-  ///
-  bool use_empty() const { return UseList == NULL; }
+  /// Return true if there are no uses of this node.
+  bool use_empty() const { return UseList == nullptr; }
 
-  /// hasOneUse - Return true if there is exactly one use of this node.
-  ///
+  /// Return true if there is exactly one use of this node.
   bool hasOneUse() const {
     return !use_empty() && std::next(use_begin()) == use_end();
   }
 
-  /// use_size - Return the number of uses of this node. This method takes
+  /// Return the number of uses of this node. This method takes
   /// time proportional to the number of uses.
-  ///
   size_t use_size() const { return std::distance(use_begin(), use_end()); }
 
-  /// getNodeId - Return the unique node id.
-  ///
+  /// Return the unique node id.
   int getNodeId() const { return NodeId; }
 
-  /// setNodeId - Set unique node id.
+  /// Set unique node id.
   void setNodeId(int Id) { NodeId = Id; }
 
-  /// getIROrder - Return the node ordering.
-  ///
+  /// Return the node ordering.
   unsigned getIROrder() const { return IROrder; }
 
-  /// setIROrder - Set the node ordering.
-  ///
+  /// Set the node ordering.
   void setIROrder(unsigned Order) { IROrder = Order; }
 
-  /// getDebugLoc - Return the source location info.
-  const DebugLoc getDebugLoc() const { return debugLoc; }
+  /// Return the source location info.
+  const DebugLoc &getDebugLoc() const { return debugLoc; }
 
-  /// setDebugLoc - Set source location info.  Try to avoid this, putting
+  /// Set source location info.  Try to avoid this, putting
   /// it in the constructor is preferable.
-  void setDebugLoc(const DebugLoc dl) { debugLoc = dl; }
+  void setDebugLoc(DebugLoc dl) { debugLoc = std::move(dl); }
 
-  /// use_iterator - This class provides iterator support for SDUse
+  /// This class provides iterator support for SDUse
   /// operands that use a specific SDNode.
   class use_iterator
     : public std::iterator<std::forward_iterator_tag, SDUse, ptrdiff_t> {
@@ -457,7 +469,7 @@ public:
                           SDUse, ptrdiff_t>::pointer pointer;
 
     use_iterator(const use_iterator &I) : Op(I.Op) {}
-    use_iterator() : Op(0) {}
+    use_iterator() : Op(nullptr) {}
 
     bool operator==(const use_iterator &x) const {
       return Op == x.Op;
@@ -466,8 +478,8 @@ public:
       return !operator==(x);
     }
 
-    /// atEnd - return true if this iterator is at the end of uses list.
-    bool atEnd() const { return Op == 0; }
+    /// Return true if this iterator is at the end of uses list.
+    bool atEnd() const { return Op == nullptr; }
 
     // Iterator traversal: forward iteration only.
     use_iterator &operator++() {          // Preincrement
@@ -490,55 +502,55 @@ public:
 
     SDUse &getUse() const { return *Op; }
 
-    /// getOperandNo - Retrieve the operand # of this use in its user.
-    ///
+    /// Retrieve the operand # of this use in its user.
     unsigned getOperandNo() const {
       assert(Op && "Cannot dereference end iterator!");
       return (unsigned)(Op - Op->getUser()->OperandList);
     }
   };
 
-  /// use_begin/use_end - Provide iteration support to walk over all uses
-  /// of an SDNode.
-
+  /// Provide iteration support to walk over all uses of an SDNode.
   use_iterator use_begin() const {
     return use_iterator(UseList);
   }
 
-  static use_iterator use_end() { return use_iterator(0); }
+  static use_iterator use_end() { return use_iterator(nullptr); }
 
+  inline iterator_range<use_iterator> uses() {
+    return iterator_range<use_iterator>(use_begin(), use_end());
+  }
+  inline iterator_range<use_iterator> uses() const {
+    return iterator_range<use_iterator>(use_begin(), use_end());
+  }
 
-  /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
-  /// indicated value.  This method ignores uses of other values defined by this
-  /// operation.
+  /// Return true if there are exactly NUSES uses of the indicated value.
+  /// This method ignores uses of other values defined by this operation.
   bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
 
-  /// hasAnyUseOfValue - Return true if there are any use of the indicated
-  /// value. This method ignores uses of other values defined by this operation.
+  /// Return true if there are any use of the indicated value.
+  /// This method ignores uses of other values defined by this operation.
   bool hasAnyUseOfValue(unsigned Value) const;
 
-  /// isOnlyUserOf - Return true if this node is the only use of N.
-  ///
+  /// Return true if this node is the only use of N.
   bool isOnlyUserOf(SDNode *N) const;
 
-  /// isOperandOf - Return true if this node is an operand of N.
-  ///
+  /// Return true if this node is an operand of N.
   bool isOperandOf(SDNode *N) const;
 
-  /// isPredecessorOf - Return true if this node is a predecessor of N.
+  /// Return true if this node is a predecessor of N.
   /// NOTE: Implemented on top of hasPredecessor and every bit as
   /// expensive. Use carefully.
   bool isPredecessorOf(const SDNode *N) const {
     return N->hasPredecessor(this);
   }
 
-  /// hasPredecessor - Return true if N is a predecessor of this node.
+  /// Return true if N is a predecessor of this node.
   /// N is either an operand of this node, or can be reached by recursively
   /// traversing up the operands.
   /// NOTE: This is an expensive method. Use it carefully.
   bool hasPredecessor(const SDNode *N) const;
 
-  /// hasPredecesorHelper - Return true if N is a predecessor of this node.
+  /// Return true if N is a predecessor of this node.
   /// N is either an operand of this node, or can be reached by recursively
   /// traversing up the operands.
   /// In this helper the Visited and worklist sets are held externally to
@@ -548,15 +560,13 @@ public:
   /// changes.
   /// NOTE: This is still very expensive. Use carefully.
   bool hasPredecessorHelper(const SDNode *N,
-                            SmallPtrSet<const SDNode *, 32> &Visited,
+                            SmallPtrSetImpl<const SDNode *> &Visited,
                             SmallVectorImpl<const SDNode *> &Worklist) const;
 
-  /// getNumOperands - Return the number of values used by this operation.
-  ///
+  /// Return the number of values used by this operation.
   unsigned getNumOperands() const { return NumOperands; }
 
-  /// getConstantOperandVal - Helper method returns the integer value of a
-  /// ConstantSDNode operand.
+  /// Helper method returns the integer value of a ConstantSDNode operand.
   uint64_t getConstantOperandVal(unsigned Num) const;
 
   const SDValue &getOperand(unsigned Num) const {
@@ -567,19 +577,20 @@ public:
   typedef SDUse* op_iterator;
   op_iterator op_begin() const { return OperandList; }
   op_iterator op_end() const { return OperandList+NumOperands; }
+  ArrayRef<SDUse> ops() const { return makeArrayRef(op_begin(), op_end()); }
 
   SDVTList getVTList() const {
     SDVTList X = { ValueList, NumValues };
     return X;
   }
 
-  /// getGluedNode - If this node has a glue operand, return the node
+  /// If this node has a glue operand, return the node
   /// to which the glue operand points. Otherwise return NULL.
   SDNode *getGluedNode() const {
     if (getNumOperands() != 0 &&
       getOperand(getNumOperands()-1).getValueType() == MVT::Glue)
       return getOperand(getNumOperands()-1).getNode();
-    return 0;
+    return nullptr;
   }
 
   // If this is a pseudo op, like copyfromreg, look to see if there is a
@@ -598,35 +609,30 @@ public:
     return FoundNode;
   }
 
-  /// getGluedUser - If this node has a glue value with a user, return
+  /// If this node has a glue value with a user, return
   /// the user (there is at most one). Otherwise return NULL.
   SDNode *getGluedUser() const {
     for (use_iterator UI = use_begin(), UE = use_end(); UI != UE; ++UI)
       if (UI.getUse().get().getValueType() == MVT::Glue)
         return *UI;
-    return 0;
+    return nullptr;
   }
 
-  /// getNumValues - Return the number of values defined/returned by this
-  /// operator.
-  ///
+  /// Return the number of values defined/returned by this operator.
   unsigned getNumValues() const { return NumValues; }
 
-  /// getValueType - Return the type of a specified result.
-  ///
+  /// Return the type of a specified result.
   EVT getValueType(unsigned ResNo) const {
     assert(ResNo < NumValues && "Illegal result number!");
     return ValueList[ResNo];
   }
 
   /// Return the type of a specified result as a simple type.
-  ///
   MVT getSimpleValueType(unsigned ResNo) const {
     return getValueType(ResNo).getSimpleVT();
   }
 
-  /// getValueSizeInBits - Returns MVT::getSizeInBits(getValueType(ResNo)).
-  ///
+  /// Returns MVT::getSizeInBits(getValueType(ResNo)).
   unsigned getValueSizeInBits(unsigned ResNo) const {
     return getValueType(ResNo).getSizeInBits();
   }
@@ -635,69 +641,66 @@ public:
   value_iterator value_begin() const { return ValueList; }
   value_iterator value_end() const { return ValueList+NumValues; }
 
-  /// getOperationName - Return the opcode of this operation for printing.
-  ///
-  std::string getOperationName(const SelectionDAG *G = 0) const;
+  /// Return the opcode of this operation for printing.
+  std::string getOperationName(const SelectionDAG *G = nullptr) const;
   static const char* getIndexedModeName(ISD::MemIndexedMode AM);
   void print_types(raw_ostream &OS, const SelectionDAG *G) const;
   void print_details(raw_ostream &OS, const SelectionDAG *G) const;
-  void print(raw_ostream &OS, const SelectionDAG *G = 0) const;
-  void printr(raw_ostream &OS, const SelectionDAG *G = 0) const;
+  void print(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
+  void printr(raw_ostream &OS, const SelectionDAG *G = nullptr) const;
 
-  /// printrFull - Print a SelectionDAG node and all children down to
+  /// Print a SelectionDAG node and all children down to
   /// the leaves.  The given SelectionDAG allows target-specific nodes
   /// to be printed in human-readable form.  Unlike printr, this will
   /// print the whole DAG, including children that appear multiple
   /// times.
   ///
-  void printrFull(raw_ostream &O, const SelectionDAG *G = 0) const;
+  void printrFull(raw_ostream &O, const SelectionDAG *G = nullptr) const;
 
-  /// printrWithDepth - Print a SelectionDAG node and children up to
+  /// Print a SelectionDAG node and children up to
   /// depth "depth."  The given SelectionDAG allows target-specific
   /// nodes to be printed in human-readable form.  Unlike printr, this
   /// will print children that appear multiple times wherever they are
   /// used.
   ///
-  void printrWithDepth(raw_ostream &O, const SelectionDAG *G = 0,
+  void printrWithDepth(raw_ostream &O, const SelectionDAG *G = nullptr,
                        unsigned depth = 100) const;
 
 
-  /// dump - Dump this node, for debugging.
+  /// Dump this node, for debugging.
   void dump() const;
 
-  /// dumpr - Dump (recursively) this node and its use-def subgraph.
+  /// Dump (recursively) this node and its use-def subgraph.
   void dumpr() const;
 
-  /// dump - Dump this node, for debugging.
+  /// Dump this node, for debugging.
   /// The given SelectionDAG allows target-specific nodes to be printed
   /// in human-readable form.
   void dump(const SelectionDAG *G) const;
 
-  /// dumpr - Dump (recursively) this node and its use-def subgraph.
+  /// Dump (recursively) this node and its use-def subgraph.
   /// The given SelectionDAG allows target-specific nodes to be printed
   /// in human-readable form.
   void dumpr(const SelectionDAG *G) const;
 
-  /// dumprFull - printrFull to dbgs().  The given SelectionDAG allows
+  /// printrFull to dbgs().  The given SelectionDAG allows
   /// target-specific nodes to be printed in human-readable form.
   /// Unlike dumpr, this will print the whole DAG, including children
   /// that appear multiple times.
-  ///
-  void dumprFull(const SelectionDAG *G = 0) const;
+  void dumprFull(const SelectionDAG *G = nullptr) const;
 
-  /// dumprWithDepth - printrWithDepth to dbgs().  The given
+  /// printrWithDepth to dbgs().  The given
   /// SelectionDAG allows target-specific nodes to be printed in
   /// human-readable form.  Unlike dumpr, this will print children
   /// that appear multiple times wherever they are used.
   ///
-  void dumprWithDepth(const SelectionDAG *G = 0, unsigned depth = 100) const;
+  void dumprWithDepth(const SelectionDAG *G = nullptr,
+                      unsigned depth = 100) const;
 
-  /// Profile - Gather unique data for the node.
-  ///
+  /// Gather unique data for the node.
   void Profile(FoldingSetNodeID &ID) const;
 
-  /// addUse - This method should only be used by the SDUse class.
-  ///
+  /// This method should only be used by the SDUse class.
   void addUse(SDUse &U) { U.addToList(&UseList); }
 
 protected:
@@ -706,15 +709,20 @@ protected:
     return Ret;
   }
 
-  SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs,
-         const SDValue *Ops, unsigned NumOps)
-    : NodeType(Opc), OperandsNeedDelete(true), HasDebugValue(false),
-      SubclassData(0), NodeId(-1),
-      OperandList(NumOps ? new SDUse[NumOps] : 0),
-      ValueList(VTs.VTs), UseList(NULL),
-      NumOperands(NumOps), NumValues(VTs.NumVTs),
-      debugLoc(dl), IROrder(Order) {
-    for (unsigned i = 0; i != NumOps; ++i) {
+  SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+         ArrayRef<SDValue> Ops)
+      : NodeType(Opc), OperandsNeedDelete(true), HasDebugValue(false),
+        SubclassData(0), NodeId(-1),
+        OperandList(Ops.size() ? new SDUse[Ops.size()] : nullptr),
+        ValueList(VTs.VTs), UseList(nullptr), NumOperands(Ops.size()),
+        NumValues(VTs.NumVTs), debugLoc(std::move(dl)), IROrder(Order) {
+    assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
+    assert(NumOperands == Ops.size() &&
+           "NumOperands wasn't wide enough for its operands!");
+    assert(NumValues == VTs.NumVTs &&
+           "NumValues wasn't wide enough for its operands!");
+    for (unsigned i = 0; i != Ops.size(); ++i) {
+      assert(OperandList && "no operands available");
       OperandList[i].setUser(this);
       OperandList[i].setInitial(Ops[i]);
     }
@@ -723,13 +731,17 @@ protected:
 
   /// This constructor adds no operands itself; operands can be
   /// set later with InitOperands.
-  SDNode(unsigned Opc, unsigned Order, const DebugLoc dl, SDVTList VTs)
-    : NodeType(Opc), OperandsNeedDelete(false), HasDebugValue(false),
-      SubclassData(0), NodeId(-1), OperandList(0),
-      ValueList(VTs.VTs), UseList(NULL), NumOperands(0), NumValues(VTs.NumVTs),
-      debugLoc(dl), IROrder(Order) {}
+  SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs)
+      : NodeType(Opc), OperandsNeedDelete(false), HasDebugValue(false),
+        SubclassData(0), NodeId(-1), OperandList(nullptr), ValueList(VTs.VTs),
+        UseList(nullptr), NumOperands(0), NumValues(VTs.NumVTs),
+        debugLoc(std::move(dl)), IROrder(Order) {
+    assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
+    assert(NumValues == VTs.NumVTs &&
+           "NumValues wasn't wide enough for its operands!");
+  }
 
-  /// InitOperands - Initialize the operands list of this with 1 operand.
+  /// Initialize the operands list of this with 1 operand.
   void InitOperands(SDUse *Ops, const SDValue &Op0) {
     Ops[0].setUser(this);
     Ops[0].setInitial(Op0);
@@ -738,7 +750,7 @@ protected:
     checkForCycles(this);
   }
 
-  /// InitOperands - Initialize the operands list of this with 2 operands.
+  /// Initialize the operands list of this with 2 operands.
   void InitOperands(SDUse *Ops, const SDValue &Op0, const SDValue &Op1) {
     Ops[0].setUser(this);
     Ops[0].setInitial(Op0);
@@ -749,7 +761,7 @@ protected:
     checkForCycles(this);
   }
 
-  /// InitOperands - Initialize the operands list of this with 3 operands.
+  /// Initialize the operands list of this with 3 operands.
   void InitOperands(SDUse *Ops, const SDValue &Op0, const SDValue &Op1,
                     const SDValue &Op2) {
     Ops[0].setUser(this);
@@ -763,7 +775,7 @@ protected:
     checkForCycles(this);
   }
 
-  /// InitOperands - Initialize the operands list of this with 4 operands.
+  /// Initialize the operands list of this with 4 operands.
   void InitOperands(SDUse *Ops, const SDValue &Op0, const SDValue &Op1,
                     const SDValue &Op2, const SDValue &Op3) {
     Ops[0].setUser(this);
@@ -779,19 +791,20 @@ protected:
     checkForCycles(this);
   }
 
-  /// InitOperands - Initialize the operands list of this with N operands.
+  /// Initialize the operands list of this with N operands.
   void InitOperands(SDUse *Ops, const SDValue *Vals, unsigned N) {
     for (unsigned i = 0; i != N; ++i) {
       Ops[i].setUser(this);
       Ops[i].setInitial(Vals[i]);
     }
     NumOperands = N;
+    assert(NumOperands == N &&
+           "NumOperands wasn't wide enough for its operands!");
     OperandList = Ops;
     checkForCycles(this);
   }
 
-  /// DropOperands - Release the operands and set this node to have
-  /// zero operands.
+  /// Release the operands and set this node to have zero operands.
   void DropOperands();
 };
 
@@ -812,7 +825,7 @@ private:
   int IROrder;
 
 public:
-  SDLoc() : Ptr(NULL), IROrder(0) {}
+  SDLoc() : Ptr(nullptr), IROrder(0) {}
   SDLoc(const SDNode *N) : Ptr(N), IROrder(-1) {
     assert(N && "null SDNode");
   }
@@ -823,14 +836,14 @@ public:
     assert(Order >= 0 && "bad IROrder");
   }
   unsigned getIROrder() {
-    if (IROrder >= 0 || Ptr == NULL) {
+    if (IROrder >= 0 || Ptr == nullptr) {
       return (unsigned)IROrder;
     }
     const SDNode *N = (const SDNode*)(Ptr);
     return N->getIROrder();
   }
   DebugLoc getDebugLoc() {
-    if (Ptr == NULL) {
+    if (!Ptr) {
       return DebugLoc();
     }
     if (IROrder >= 0) {
@@ -845,6 +858,13 @@ public:
 
 // Define inline functions from the SDValue class.
 
+inline SDValue::SDValue(SDNode *node, unsigned resno)
+    : Node(node), ResNo(resno) {
+  assert((!Node || ResNo < Node->getNumValues()) &&
+         "Invalid result number for the given node!");
+  assert(ResNo < -2U && "Cannot use result numbers reserved for DenseMaps.");
+}
+
 inline unsigned SDValue::getOpcode() const {
   return Node->getOpcode();
 }
@@ -878,7 +898,7 @@ inline bool SDValue::use_empty() const {
 inline bool SDValue::hasOneUse() const {
   return Node->hasNUsesOfValue(1, ResNo);
 }
-inline const DebugLoc SDValue::getDebugLoc() const {
+inline const DebugLoc &SDValue::getDebugLoc() const {
   return Node->getDebugLoc();
 }
 inline void SDValue::dump() const {
@@ -906,7 +926,63 @@ inline void SDUse::setNode(SDNode *N) {
   if (N) N->addUse(*this);
 }
 
-/// UnarySDNode - This class is used for single-operand SDNodes.  This is solely
+/// These are IR-level optimization flags that may be propagated to SDNodes.
+/// TODO: This data structure should be shared by the IR optimizer and the
+/// the backend.
+struct SDNodeFlags {
+private:
+  bool NoUnsignedWrap : 1;
+  bool NoSignedWrap : 1;
+  bool Exact : 1;
+  bool UnsafeAlgebra : 1;
+  bool NoNaNs : 1;
+  bool NoInfs : 1;
+  bool NoSignedZeros : 1;
+  bool AllowReciprocal : 1;
+
+public:
+  /// Default constructor turns off all optimization flags.
+  SDNodeFlags() {
+    NoUnsignedWrap = false;
+    NoSignedWrap = false;
+    Exact = false;
+    UnsafeAlgebra = false;
+    NoNaNs = false;
+    NoInfs = false;
+    NoSignedZeros = false;
+    AllowReciprocal = false;
+  }
+
+  // These are mutators for each flag.
+  void setNoUnsignedWrap(bool b) { NoUnsignedWrap = b; }
+  void setNoSignedWrap(bool b) { NoSignedWrap = b; }
+  void setExact(bool b) { Exact = b; }
+  void setUnsafeAlgebra(bool b) { UnsafeAlgebra = b; }
+  void setNoNaNs(bool b) { NoNaNs = b; }
+  void setNoInfs(bool b) { NoInfs = b; }
+  void setNoSignedZeros(bool b) { NoSignedZeros = b; }
+  void setAllowReciprocal(bool b) { AllowReciprocal = b; }
+
+  // These are accessors for each flag.
+  bool hasNoUnsignedWrap() const { return NoUnsignedWrap; }
+  bool hasNoSignedWrap() const { return NoSignedWrap; }
+  bool hasExact() const { return Exact; }
+  bool hasUnsafeAlgebra() const { return UnsafeAlgebra; }
+  bool hasNoNaNs() const { return NoNaNs; }
+  bool hasNoInfs() const { return NoInfs; }
+  bool hasNoSignedZeros() const { return NoSignedZeros; }
+  bool hasAllowReciprocal() const { return AllowReciprocal; }
+
+  /// Return a raw encoding of the flags.
+  /// This function should only be used to add data to the NodeID value.
+  unsigned getRawFlags() const {
+    return (NoUnsignedWrap << 0) | (NoSignedWrap << 1) | (Exact << 2) |
+           (UnsafeAlgebra << 3) | (NoNaNs << 4) | (NoInfs << 5) |
+           (NoSignedZeros << 6) | (AllowReciprocal << 7);
+  }
+};
+
+/// This class is used for single-operand SDNodes.  This is solely
 /// to allow co-allocation of node operands with the node itself.
 class UnarySDNode : public SDNode {
   SDUse Op;
@@ -918,7 +994,7 @@ public:
   }
 };
 
-/// BinarySDNode - This class is used for two-operand SDNodes.  This is solely
+/// This class is used for two-operand SDNodes.  This is solely
 /// to allow co-allocation of node operands with the node itself.
 class BinarySDNode : public SDNode {
   SDUse Ops[2];
@@ -930,7 +1006,37 @@ public:
   }
 };
 
-/// TernarySDNode - This class is used for three-operand SDNodes. This is solely
+/// Returns true if the opcode is a binary operation with flags.
+static bool isBinOpWithFlags(unsigned Opcode) {
+  switch (Opcode) {
+  case ISD::SDIV:
+  case ISD::UDIV:
+  case ISD::SRA:
+  case ISD::SRL:
+  case ISD::MUL:
+  case ISD::ADD:
+  case ISD::SUB:
+  case ISD::SHL:
+    return true;
+  default:
+    return false;
+  }
+}
+
+/// This class is an extension of BinarySDNode
+/// used from those opcodes that have associated extra flags.
+class BinaryWithFlagsSDNode : public BinarySDNode {
+public:
+  SDNodeFlags Flags;
+  BinaryWithFlagsSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
+                        SDValue X, SDValue Y)
+      : BinarySDNode(Opc, Order, dl, VTs, X, Y), Flags() {}
+  static bool classof(const SDNode *N) {
+    return isBinOpWithFlags(N->getOpcode());
+  }
+};
+
+/// This class is used for three-operand SDNodes. This is solely
 /// to allow co-allocation of node operands with the node itself.
 class TernarySDNode : public SDNode {
   SDUse Ops[3];
@@ -943,7 +1049,7 @@ public:
 };
 
 
-/// HandleSDNode - This class is used to form a handle around another node that
+/// This class is used to form a handle around another node that
 /// is persistent and is updated across invocations of replaceAllUsesWith on its
 /// operand.  This node should be directly created by end-users and not added to
 /// the AllNodes list.
@@ -978,11 +1084,11 @@ public:
 /// Abstact virtual class for operations for memory operations
 class MemSDNode : public SDNode {
 private:
-  // MemoryVT - VT of in-memory value.
+  // VT of in-memory value.
   EVT MemoryVT;
 
 protected:
-  /// MMO - Memory reference information.
+  /// Memory reference information.
   MachineMemOperand *MMO;
 
 public:
@@ -990,8 +1096,7 @@ public:
             EVT MemoryVT, MachineMemOperand *MMO);
 
   MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
-            const SDValue *Ops,
-            unsigned NumOps, EVT MemoryVT, MachineMemOperand *MMO);
+            ArrayRef<SDValue> Ops, EVT MemoryVT, MachineMemOperand *MMO);
 
   bool readMem() const { return MMO->isLoad(); }
   bool writeMem() const { return MMO->isStore(); }
@@ -1004,7 +1109,7 @@ public:
     return MMO->getAlignment();
   }
 
-  /// getRawSubclassData - Return the SubclassData value, which contains an
+  /// Return the SubclassData value, which contains an
   /// encoding of the volatile flag, as well as bits used by subclasses. This
   /// function should only be used to compute a FoldingSetNodeID value.
   unsigned getRawSubclassData() const {
@@ -1024,20 +1129,19 @@ public:
     return SynchronizationScope((SubclassData >> 12) & 1);
   }
 
-  /// Returns the SrcValue and offset that describes the location of the access
-  const Value *getSrcValue() const { return MMO->getValue(); }
+  // Returns the offset from the location of the access.
   int64_t getSrcValueOffset() const { return MMO->getOffset(); }
 
-  /// Returns the TBAAInfo that describes the dereference.
-  const MDNode *getTBAAInfo() const { return MMO->getTBAAInfo(); }
+  /// Returns the AA info that describes the dereference.
+  AAMDNodes getAAInfo() const { return MMO->getAAInfo(); }
 
   /// Returns the Ranges that describes the dereference.
   const MDNode *getRanges() const { return MMO->getRanges(); }
 
-  /// getMemoryVT - Return the type of the in-memory value.
+  /// Return the type of the in-memory value.
   EVT getMemoryVT() const { return MemoryVT; }
 
-  /// getMemOperand - Return a MachineMemOperand object describing the memory
+  /// Return a MachineMemOperand object describing the memory
   /// reference performed by operation.
   MachineMemOperand *getMemOperand() const { return MMO; }
 
@@ -1045,12 +1149,12 @@ public:
     return MMO->getPointerInfo();
   }
 
-  /// getAddressSpace - Return the address space for the associated pointer
+  /// Return the address space for the associated pointer
   unsigned getAddressSpace() const {
     return getPointerInfo().getAddrSpace();
   }
 
-  /// refineAlignment - Update this MemSDNode's MachineMemOperand information
+  /// Update this MemSDNode's MachineMemOperand information
   /// to reflect the alignment of NewMMO, if it has a greater alignment.
   /// This must only be used when the new alignment applies to all users of
   /// this MachineMemOperand.
@@ -1071,6 +1175,7 @@ public:
            N->getOpcode() == ISD::STORE               ||
            N->getOpcode() == ISD::PREFETCH            ||
            N->getOpcode() == ISD::ATOMIC_CMP_SWAP     ||
+           N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
            N->getOpcode() == ISD::ATOMIC_SWAP         ||
            N->getOpcode() == ISD::ATOMIC_LOAD_ADD     ||
            N->getOpcode() == ISD::ATOMIC_LOAD_SUB     ||
@@ -1084,12 +1189,16 @@ public:
            N->getOpcode() == ISD::ATOMIC_LOAD_UMAX    ||
            N->getOpcode() == ISD::ATOMIC_LOAD         ||
            N->getOpcode() == ISD::ATOMIC_STORE        ||
+           N->getOpcode() == ISD::MLOAD               ||
+           N->getOpcode() == ISD::MSTORE              ||
+           N->getOpcode() == ISD::MGATHER             ||
+           N->getOpcode() == ISD::MSCATTER            ||
+           N->isMemIntrinsic()                        ||
            N->isTargetMemoryOpcode();
   }
 };
 
-/// AtomicSDNode - A SDNode reprenting atomic operations.
-///
+/// A SDNode reprenting atomic operations.
 class AtomicSDNode : public MemSDNode {
   SDUse Ops[4];
 
@@ -1153,7 +1262,7 @@ public:
     InitOperands(Ops, Chain, Ptr);
   }
   AtomicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTL, EVT MemVT,
-               SDValue* AllOps, SDUse *DynOps, unsigned NumOps,
+               const SDValue* AllOps, SDUse *DynOps, unsigned NumOps,
                MachineMemOperand *MMO,
                AtomicOrdering SuccessOrdering, AtomicOrdering FailureOrdering,
                SynchronizationScope SynchScope)
@@ -1179,12 +1288,13 @@ public:
 
   bool isCompareAndSwap() const {
     unsigned Op = getOpcode();
-    return Op == ISD::ATOMIC_CMP_SWAP;
+    return Op == ISD::ATOMIC_CMP_SWAP || Op == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS;
   }
 
   // Methods to support isa and dyn_cast
   static bool classof(const SDNode *N) {
     return N->getOpcode() == ISD::ATOMIC_CMP_SWAP     ||
+           N->getOpcode() == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS ||
            N->getOpcode() == ISD::ATOMIC_SWAP         ||
            N->getOpcode() == ISD::ATOMIC_LOAD_ADD     ||
            N->getOpcode() == ISD::ATOMIC_LOAD_SUB     ||
@@ -1201,30 +1311,30 @@ public:
   }
 };
 
-/// MemIntrinsicSDNode - This SDNode is used for target intrinsics that touch
+/// This SDNode is used for target intrinsics that touch
 /// memory and need an associated MachineMemOperand. Its opcode may be
 /// INTRINSIC_VOID, INTRINSIC_W_CHAIN, PREFETCH, or a target-specific opcode
 /// with a value not less than FIRST_TARGET_MEMORY_OPCODE.
 class MemIntrinsicSDNode : public MemSDNode {
 public:
   MemIntrinsicSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
-                     const SDValue *Ops, unsigned NumOps,
-                     EVT MemoryVT, MachineMemOperand *MMO)
-    : MemSDNode(Opc, Order, dl, VTs, Ops, NumOps, MemoryVT, MMO) {
+                     ArrayRef<SDValue> Ops, EVT MemoryVT,
+                     MachineMemOperand *MMO)
+    : MemSDNode(Opc, Order, dl, VTs, Ops, MemoryVT, MMO) {
+    SubclassData |= 1u << 13;
   }
 
   // Methods to support isa and dyn_cast
   static bool classof(const SDNode *N) {
     // We lower some target intrinsics to their target opcode
     // early a node with a target opcode can be of this class
-    return N->getOpcode() == ISD::INTRINSIC_W_CHAIN ||
-           N->getOpcode() == ISD::INTRINSIC_VOID ||
+    return N->isMemIntrinsic()             ||
            N->getOpcode() == ISD::PREFETCH ||
            N->isTargetMemoryOpcode();
   }
 };
 
-/// ShuffleVectorSDNode - This SDNode is used to implement the code generator
+/// This SDNode is used to implement the code generator
 /// support for the llvm IR shufflevector instruction.  It combines elements
 /// from two input vectors into a new input vector, with the selection and
 /// ordering of elements determined by an array of integers, referred to as
@@ -1268,6 +1378,21 @@ public:
   }
   static bool isSplatMask(const int *Mask, EVT VT);
 
+  /// Change values in a shuffle permute mask assuming
+  /// the two vector operands have swapped position.
+  static void commuteMask(SmallVectorImpl<int> &Mask) {
+    unsigned NumElems = Mask.size();
+    for (unsigned i = 0; i != NumElems; ++i) {
+      int idx = Mask[i];
+      if (idx < 0)
+        continue;
+      else if (idx < (int)NumElems)
+        Mask[i] = idx + NumElems;
+      else
+        Mask[i] = idx - NumElems;
+    }
+  }
+
   static bool classof(const SDNode *N) {
     return N->getOpcode() == ISD::VECTOR_SHUFFLE;
   }
@@ -1276,9 +1401,10 @@ public:
 class ConstantSDNode : public SDNode {
   const ConstantInt *Value;
   friend class SelectionDAG;
-  ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val, EVT VT)
+  ConstantSDNode(bool isTarget, bool isOpaque, const ConstantInt *val,
+                 DebugLoc DL, EVT VT)
     : SDNode(isTarget ? ISD::TargetConstant : ISD::Constant,
-             0, DebugLoc(), getSDVTList(VT)), Value(val) {
+             0, DL, getSDVTList(VT)), Value(val) {
     SubclassData |= (uint16_t)isOpaque;
   }
 public:
@@ -1312,13 +1438,19 @@ public:
   const APFloat& getValueAPF() const { return Value->getValueAPF(); }
   const ConstantFP *getConstantFPValue() const { return Value; }
 
-  /// isZero - Return true if the value is positive or negative zero.
+  /// Return true if the value is positive or negative zero.
   bool isZero() const { return Value->isZero(); }
 
-  /// isNaN - Return true if the value is a NaN.
+  /// Return true if the value is a NaN.
   bool isNaN() const { return Value->isNaN(); }
 
-  /// isExactlyValue - We don't rely on operator== working on double values, as
+  /// Return true if the value is an infinity
+  bool isInfinity() const { return Value->isInfinity(); }
+
+  /// Return true if the value is negative.
+  bool isNegative() const { return Value->isNegative(); }
+
+  /// We don't rely on operator== working on double values, as
   /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
   /// As such, this method can be used to do an exact bit-for-bit comparison of
   /// two floating point values.
@@ -1502,13 +1634,12 @@ public:
   }
 };
 
-/// BuildVectorSDNode - A "pseudo-class" with methods for operating on
-/// BUILD_VECTORs.
+/// A "pseudo-class" with methods for operating on BUILD_VECTORs.
 class BuildVectorSDNode : public SDNode {
   // These are constructed as SDNodes and then cast to BuildVectorSDNodes.
-  explicit BuildVectorSDNode() LLVM_DELETED_FUNCTION;
+  explicit BuildVectorSDNode() = delete;
 public:
-  /// isConstantSplat - Check if this is a constant splat, and if so, find the
+  /// Check if this is a constant splat, and if so, find the
   /// smallest element size that splats the vector.  If MinSplatBits is
   /// nonzero, the element size must be at least that large.  Note that the
   /// splat element may be the entire vector (i.e., a one element vector).
@@ -1522,10 +1653,27 @@ public:
                        unsigned MinSplatBits = 0,
                        bool isBigEndian = false) const;
 
-  /// isConstantSplat - Simpler form of isConstantSplat. Get the constant splat
-  /// when you only care about the value. Returns nullptr if this isn't a
-  /// constant splat vector.
-  ConstantSDNode *isConstantSplat() const;
+  /// \brief Returns the splatted value or a null value if this is not a splat.
+  ///
+  /// If passed a non-null UndefElements bitvector, it will resize it to match
+  /// the vector width and set the bits where elements are undef.
+  SDValue getSplatValue(BitVector *UndefElements = nullptr) const;
+
+  /// \brief Returns the splatted constant or null if this is not a constant
+  /// splat.
+  ///
+  /// If passed a non-null UndefElements bitvector, it will resize it to match
+  /// the vector width and set the bits where elements are undef.
+  ConstantSDNode *
+  getConstantSplatNode(BitVector *UndefElements = nullptr) const;
+
+  /// \brief Returns the splatted constant FP or null if this is not a constant
+  /// FP splat.
+  ///
+  /// If passed a non-null UndefElements bitvector, it will resize it to match
+  /// the vector width and set the bits where elements are undef.
+  ConstantFPSDNode *
+  getConstantFPSplatNode(BitVector *UndefElements = nullptr) const;
 
   bool isConstant() const;
 
@@ -1534,7 +1682,7 @@ public:
   }
 };
 
-/// SrcValueSDNode - An SDNode that holds an arbitrary LLVM IR Value. This is
+/// An SDNode that holds an arbitrary LLVM IR Value. This is
 /// used when the SelectionDAG needs to make a simple reference to something
 /// in the LLVM IR representation.
 ///
@@ -1546,7 +1694,7 @@ class SrcValueSDNode : public SDNode {
     : SDNode(ISD::SRCVALUE, 0, DebugLoc(), getSDVTList(MVT::Other)), V(v) {}
 
 public:
-  /// getValue - return the contained Value.
+  /// Return the contained Value.
   const Value *getValue() const { return V; }
 
   static bool classof(const SDNode *N) {
@@ -1673,17 +1821,16 @@ public:
   }
 };
 
-/// CvtRndSatSDNode - NOTE: avoid using this node as this may disappear in the
+/// NOTE: avoid using this node as this may disappear in the
 /// future and most targets don't support it.
 class CvtRndSatSDNode : public SDNode {
   ISD::CvtCode CvtCode;
   friend class SelectionDAG;
   explicit CvtRndSatSDNode(EVT VT, unsigned Order, DebugLoc dl,
-                           const SDValue *Ops, unsigned NumOps,
-                           ISD::CvtCode Code)
-    : SDNode(ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops, NumOps),
+                           ArrayRef<SDValue> Ops, ISD::CvtCode Code)
+    : SDNode(ISD::CONVERT_RNDSAT, Order, dl, getSDVTList(VT), Ops),
       CvtCode(Code) {
-    assert(NumOps == 5 && "wrong number of operations");
+    assert(Ops.size() == 5 && "wrong number of operations");
   }
 public:
   ISD::CvtCode getCvtCode() const { return CvtCode; }
@@ -1693,7 +1840,7 @@ public:
   }
 };
 
-/// VTSDNode - This class is used to represent EVT's, which are used
+/// This class is used to represent EVT's, which are used
 /// to parameterize some operations.
 class VTSDNode : public SDNode {
   EVT ValueType;
@@ -1711,8 +1858,7 @@ public:
   }
 };
 
-/// LSBaseSDNode - Base class for LoadSDNode and StoreSDNode
-///
+/// Base class for LoadSDNode and StoreSDNode
 class LSBaseSDNode : public MemSDNode {
   //! Operand array for load and store
   /*!
@@ -1738,16 +1884,16 @@ public:
     return getOperand(getOpcode() == ISD::LOAD ? 2 : 3);
   }
 
-  /// getAddressingMode - Return the addressing mode for this load or store:
+  /// Return the addressing mode for this load or store:
   /// unindexed, pre-inc, pre-dec, post-inc, or post-dec.
   ISD::MemIndexedMode getAddressingMode() const {
     return ISD::MemIndexedMode((SubclassData >> 2) & 7);
   }
 
-  /// isIndexed - Return true if this is a pre/post inc/dec load/store.
+  /// Return true if this is a pre/post inc/dec load/store.
   bool isIndexed() const { return getAddressingMode() != ISD::UNINDEXED; }
 
-  /// isUnindexed - Return true if this is NOT a pre/post inc/dec load/store.
+  /// Return true if this is NOT a pre/post inc/dec load/store.
   bool isUnindexed() const { return getAddressingMode() == ISD::UNINDEXED; }
 
   static bool classof(const SDNode *N) {
@@ -1756,8 +1902,7 @@ public:
   }
 };
 
-/// LoadSDNode - This class is used to represent ISD::LOAD nodes.
-///
+/// This class is used to represent ISD::LOAD nodes.
 class LoadSDNode : public LSBaseSDNode {
   friend class SelectionDAG;
   LoadSDNode(SDValue *ChainPtrOff, unsigned Order, DebugLoc dl, SDVTList VTs,
@@ -1771,7 +1916,7 @@ class LoadSDNode : public LSBaseSDNode {
   }
 public:
 
-  /// getExtensionType - Return whether this is a plain node,
+  /// Return whether this is a plain node,
   /// or one of the varieties of value-extending loads.
   ISD::LoadExtType getExtensionType() const {
     return ISD::LoadExtType(SubclassData & 3);
@@ -1785,8 +1930,7 @@ public:
   }
 };
 
-/// StoreSDNode - This class is used to represent ISD::STORE nodes.
-///
+/// This class is used to represent ISD::STORE nodes.
 class StoreSDNode : public LSBaseSDNode {
   friend class SelectionDAG;
   StoreSDNode(SDValue *ChainValuePtrOff, unsigned Order, DebugLoc dl,
@@ -1801,7 +1945,7 @@ class StoreSDNode : public LSBaseSDNode {
   }
 public:
 
-  /// isTruncatingStore - Return true if the op does a truncation before store.
+  /// Return true if the op does a truncation before store.
   /// For integers this is the same as doing a TRUNCATE and storing the result.
   /// For floats, it is the same as doing an FP_ROUND and storing the result.
   bool isTruncatingStore() const { return SubclassData & 1; }
@@ -1815,10 +1959,156 @@ public:
   }
 };
 
-/// MachineSDNode - An SDNode that represents everything that will be needed
+/// This base class is used to represent MLOAD and MSTORE nodes
+class MaskedLoadStoreSDNode : public MemSDNode {
+  // Operands
+  SDUse Ops[4];
+public:
+  friend class SelectionDAG;
+  MaskedLoadStoreSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl,
+                   SDValue *Operands, unsigned numOperands, 
+                   SDVTList VTs, EVT MemVT, MachineMemOperand *MMO)
+    : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
+    InitOperands(Ops, Operands, numOperands);
+  }
+
+  // In the both nodes address is Op1, mask is Op2:
+  // MaskedLoadSDNode (Chain, ptr, mask, src0), src0 is a passthru value
+  // MaskedStoreSDNode (Chain, ptr, mask, data)
+  // Mask is a vector of i1 elements
+  const SDValue &getBasePtr() const { return getOperand(1); }
+  const SDValue &getMask() const    { return getOperand(2); }
+
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::MLOAD ||
+           N->getOpcode() == ISD::MSTORE;
+  }
+};
+
+/// This class is used to represent an MLOAD node
+class MaskedLoadSDNode : public MaskedLoadStoreSDNode {
+public:
+  friend class SelectionDAG;
+  MaskedLoadSDNode(unsigned Order, DebugLoc dl, SDValue *Operands,
+                   unsigned numOperands, SDVTList VTs, ISD::LoadExtType ETy,
+                   EVT MemVT, MachineMemOperand *MMO)
+    : MaskedLoadStoreSDNode(ISD::MLOAD, Order, dl, Operands, numOperands,
+                            VTs, MemVT, MMO) {
+    SubclassData |= (unsigned short)ETy;
+  }
+
+  ISD::LoadExtType getExtensionType() const {
+    return ISD::LoadExtType(SubclassData & 3);
+  } 
+  const SDValue &getSrc0() const { return getOperand(3); }
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::MLOAD;
+  }
+};
+
+/// This class is used to represent an MSTORE node
+class MaskedStoreSDNode : public MaskedLoadStoreSDNode {
+
+public:
+  friend class SelectionDAG;
+  MaskedStoreSDNode(unsigned Order, DebugLoc dl, SDValue *Operands,
+                    unsigned numOperands, SDVTList VTs, bool isTrunc, EVT MemVT,
+                    MachineMemOperand *MMO)
+    : MaskedLoadStoreSDNode(ISD::MSTORE, Order, dl, Operands, numOperands,
+                            VTs, MemVT, MMO) {
+      SubclassData |= (unsigned short)isTrunc;
+  }
+  /// Return true if the op does a truncation before store.
+  /// For integers this is the same as doing a TRUNCATE and storing the result.
+  /// For floats, it is the same as doing an FP_ROUND and storing the result.
+  bool isTruncatingStore() const { return SubclassData & 1; }
+
+  const SDValue &getValue() const { return getOperand(3); }
+
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::MSTORE;
+  }
+};
+
+/// This is a base class used to represent
+/// MGATHER and MSCATTER nodes
+///
+class MaskedGatherScatterSDNode : public MemSDNode {
+  // Operands
+  SDUse Ops[5];
+public:
+  friend class SelectionDAG;
+  MaskedGatherScatterSDNode(ISD::NodeType NodeTy, unsigned Order, DebugLoc dl,
+                            ArrayRef<SDValue> Operands, SDVTList VTs, EVT MemVT,
+                            MachineMemOperand *MMO)
+    : MemSDNode(NodeTy, Order, dl, VTs, MemVT, MMO) {
+    assert(Operands.size() == 5 && "Incompatible number of operands");
+    InitOperands(Ops, Operands.data(), Operands.size());
+  }
+
+  // In the both nodes address is Op1, mask is Op2:
+  // MaskedGatherSDNode  (Chain, src0, mask, base, index), src0 is a passthru value
+  // MaskedScatterSDNode (Chain, value, mask, base, index)
+  // Mask is a vector of i1 elements
+  const SDValue &getBasePtr() const { return getOperand(3); }
+  const SDValue &getIndex()   const { return getOperand(4); }
+  const SDValue &getMask()    const { return getOperand(2); }
+  const SDValue &getValue()   const { return getOperand(1); }
+
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::MGATHER ||
+           N->getOpcode() == ISD::MSCATTER;
+  }
+};
+
+/// This class is used to represent an MGATHER node
+///
+class MaskedGatherSDNode : public MaskedGatherScatterSDNode {
+public:
+  friend class SelectionDAG;
+  MaskedGatherSDNode(unsigned Order, DebugLoc dl, ArrayRef<SDValue> Operands, 
+                     SDVTList VTs, EVT MemVT, MachineMemOperand *MMO)
+    : MaskedGatherScatterSDNode(ISD::MGATHER, Order, dl, Operands, VTs, MemVT,
+                                MMO) {
+    assert(getValue().getValueType() == getValueType(0) &&
+           "Incompatible type of the PathThru value in MaskedGatherSDNode");
+    assert(getMask().getValueType().getVectorNumElements() == 
+           getValueType(0).getVectorNumElements() && 
+           "Vector width mismatch between mask and data");
+    assert(getMask().getValueType().getScalarType() == MVT::i1 && 
+           "Vector width mismatch between mask and data");
+  }
+
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::MGATHER;
+  }
+};
+
+/// This class is used to represent an MSCATTER node
+///
+class MaskedScatterSDNode : public MaskedGatherScatterSDNode {
+
+public:
+  friend class SelectionDAG;
+  MaskedScatterSDNode(unsigned Order, DebugLoc dl,ArrayRef<SDValue> Operands,
+                      SDVTList VTs, EVT MemVT, MachineMemOperand *MMO)
+    : MaskedGatherScatterSDNode(ISD::MSCATTER, Order, dl, Operands, VTs, MemVT,
+                                MMO) {
+    assert(getMask().getValueType().getVectorNumElements() == 
+           getValue().getValueType().getVectorNumElements() && 
+           "Vector width mismatch between mask and data");
+    assert(getMask().getValueType().getScalarType() == MVT::i1 && 
+           "Vector width mismatch between mask and data");
+  }
+
+  static bool classof(const SDNode *N) {
+    return N->getOpcode() == ISD::MSCATTER;
+  }
+};
+
+/// An SDNode that represents everything that will be needed
 /// to construct a MachineInstr. These nodes are created during the
 /// instruction selection proper phase.
-///
 class MachineSDNode : public SDNode {
 public:
   typedef MachineMemOperand **mmo_iterator;
@@ -1826,13 +2116,13 @@ public:
 private:
   friend class SelectionDAG;
   MachineSDNode(unsigned Opc, unsigned Order, const DebugLoc DL, SDVTList VTs)
-    : SDNode(Opc, Order, DL, VTs), MemRefs(0), MemRefsEnd(0) {}
+    : SDNode(Opc, Order, DL, VTs), MemRefs(nullptr), MemRefsEnd(nullptr) {}
 
-  /// LocalOperands - Operands for this instruction, if they fit here. If
+  /// Operands for this instruction, if they fit here. If
   /// they don't, this field is unused.
   SDUse LocalOperands[4];
 
-  /// MemRefs - Memory reference descriptions for this instruction.
+  /// Memory reference descriptions for this instruction.
   mmo_iterator MemRefs;
   mmo_iterator MemRefsEnd;
 
@@ -1841,7 +2131,7 @@ public:
   mmo_iterator memoperands_end() const { return MemRefsEnd; }
   bool memoperands_empty() const { return MemRefsEnd == MemRefs; }
 
-  /// setMemRefs - Assign this MachineSDNodes's memory reference descriptor
+  /// Assign this MachineSDNodes's memory reference descriptor
   /// list. This does not transfer ownership.
   void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd) {
     for (mmo_iterator MMI = NewMemRefs, MME = NewMemRefsEnd; MMI != MME; ++MMI)
@@ -1867,12 +2157,6 @@ public:
   }
   bool operator!=(const SDNodeIterator& x) const { return !operator==(x); }
 
-  const SDNodeIterator &operator=(const SDNodeIterator &I) {
-    assert(I.Node == Node && "Cannot assign iterators to two different nodes!");
-    Operand = I.Operand;
-    return *this;
-  }
-
   pointer operator*() const {
     return Node->getOperand(Operand).getNode();
   }
@@ -1912,60 +2196,51 @@ template <> struct GraphTraits<SDNode*> {
   }
 };
 
-/// LargestSDNode - The largest SDNode class.
-///
-typedef AtomicSDNode LargestSDNode;
+/// The largest SDNode class.
+typedef MaskedGatherScatterSDNode LargestSDNode;
 
-/// MostAlignedSDNode - The SDNode class with the greatest alignment
-/// requirement.
-///
+/// The SDNode class with the greatest alignment requirement.
 typedef GlobalAddressSDNode MostAlignedSDNode;
 
 namespace ISD {
-  /// isNormalLoad - Returns true if the specified node is a non-extending
-  /// and unindexed load.
+  /// Returns true if the specified node is a non-extending and unindexed load.
   inline bool isNormalLoad(const SDNode *N) {
     const LoadSDNode *Ld = dyn_cast<LoadSDNode>(N);
     return Ld && Ld->getExtensionType() == ISD::NON_EXTLOAD &&
       Ld->getAddressingMode() == ISD::UNINDEXED;
   }
 
-  /// isNON_EXTLoad - Returns true if the specified node is a non-extending
-  /// load.
+  /// Returns true if the specified node is a non-extending load.
   inline bool isNON_EXTLoad(const SDNode *N) {
     return isa<LoadSDNode>(N) &&
       cast<LoadSDNode>(N)->getExtensionType() == ISD::NON_EXTLOAD;
   }
 
-  /// isEXTLoad - Returns true if the specified node is a EXTLOAD.
-  ///
+  /// Returns true if the specified node is a EXTLOAD.
   inline bool isEXTLoad(const SDNode *N) {
     return isa<LoadSDNode>(N) &&
       cast<LoadSDNode>(N)->getExtensionType() == ISD::EXTLOAD;
   }
 
-  /// isSEXTLoad - Returns true if the specified node is a SEXTLOAD.
-  ///
+  /// Returns true if the specified node is a SEXTLOAD.
   inline bool isSEXTLoad(const SDNode *N) {
     return isa<LoadSDNode>(N) &&
       cast<LoadSDNode>(N)->getExtensionType() == ISD::SEXTLOAD;
   }
 
-  /// isZEXTLoad - Returns true if the specified node is a ZEXTLOAD.
-  ///
+  /// Returns true if the specified node is a ZEXTLOAD.
   inline bool isZEXTLoad(const SDNode *N) {
     return isa<LoadSDNode>(N) &&
       cast<LoadSDNode>(N)->getExtensionType() == ISD::ZEXTLOAD;
   }
 
-  /// isUNINDEXEDLoad - Returns true if the specified node is an unindexed load.
-  ///
+  /// Returns true if the specified node is an unindexed load.
   inline bool isUNINDEXEDLoad(const SDNode *N) {
     return isa<LoadSDNode>(N) &&
       cast<LoadSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;
   }
 
-  /// isNormalStore - Returns true if the specified node is a non-truncating
+  /// Returns true if the specified node is a non-truncating
   /// and unindexed store.
   inline bool isNormalStore(const SDNode *N) {
     const StoreSDNode *St = dyn_cast<StoreSDNode>(N);
@@ -1973,20 +2248,17 @@ namespace ISD {
       St->getAddressingMode() == ISD::UNINDEXED;
   }
 
-  /// isNON_TRUNCStore - Returns true if the specified node is a non-truncating
-  /// store.
+  /// Returns true if the specified node is a non-truncating store.
   inline bool isNON_TRUNCStore(const SDNode *N) {
     return isa<StoreSDNode>(N) && !cast<StoreSDNode>(N)->isTruncatingStore();
   }
 
-  /// isTRUNCStore - Returns true if the specified node is a truncating
-  /// store.
+  /// Returns true if the specified node is a truncating store.
   inline bool isTRUNCStore(const SDNode *N) {
     return isa<StoreSDNode>(N) && cast<StoreSDNode>(N)->isTruncatingStore();
   }
 
-  /// isUNINDEXEDStore - Returns true if the specified node is an
-  /// unindexed store.
+  /// Returns true if the specified node is an unindexed store.
   inline bool isUNINDEXEDStore(const SDNode *N) {
     return isa<StoreSDNode>(N) &&
       cast<StoreSDNode>(N)->getAddressingMode() == ISD::UNINDEXED;