[CodeGen] Add separate UseList for each ResNo of SDNode

[kovdan01]

Summary

It is now a common pattern to iterate over SDNode uses corresponsing to a
specific ResNo with code like this:

for (auto UI = N->use_begin(), UE = N->use_end(); UI != UE; ++UI) {
  if (UI.getUse().getResNo() != SomeValue)
    continue;
  // ...
}

It results in performance decrease when we have many ResNo's and have to
iterate over all their uses instead of only needed ones. A perfect example of
that is SDNode::hasNUsesOfValue.

This patch adds new fields to SDNode and SDUse responsible for use lists for
each ResNo separately. Keeping in mind that it increases those classes sizes,
performance testing with llvm-test-suite was done, and no noticeable issues
with compile and link timings were detected. On the contrary, when compiling
IR like this, we get a significant performance enhancement (78.4s -> 14.7s on
my machine).

%struct.large = type { [65535 x i8] }
define void @foo(%struct.large %s, %struct.large* %p) {
  store %struct.large %s, %struct.large* %p, align 1
  ret void
}

This patch will be followed by another one fixing failing assertion when
compiling code with large structs (which was the root cause of investigation
resulting in current change).

[craig.topper]

IR like this is discouraged. I think it's almost considered a historical design mistake that you can store an entire aggregate in one IR instruction.

%struct.large = type { [65535 x i8] }
define void @foo(%struct.large %s, %struct.large* %p) {
  store %struct.large %s, %struct.large* %p, align 1
  ret void
}

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

583

How many inline values does this SmallVector end up creating? 1 or 2 results is by far the most common so I wonder if we should explicitly use 2 instead of leaving it up to the SmallVector to decide.

[RKSimon]

How much has @craig.topper's hasOneUse reordering fixes had on your perf numbers?

[kovdan01]

That fixed my issue for X86, thanks! Regarding other targets - it turns out that my patch gives no performance enhancement (tested that). So abandon the revision - as for now it seems not needed anymore.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

 ///
 class SDUse {
   /// Val - The value being used.
   SDValue Val;
   /// User - The user of this value.
   SDNode *User = nullptr;
   /// Prev, Next - Pointers to the uses list of the SDNode referred by
   /// this operand.
-  SDUse **Prev = nullptr;
-  SDUse *Next = nullptr;
+  SDUse **AllUsesPrev = nullptr;
+  SDUse *AllUsesNext = nullptr;
+  SDUse **ResNoUsesPrev = nullptr;
+  SDUse *ResNoUsesNext = nullptr;
 
 public:
   SDUse() = default;
   SDUse(const SDUse &U) = delete;
   SDUse &operator=(const SDUse &) = delete;
 
   /// Normally SDUse will just implicitly convert to an SDValue that it holds.
   operator const SDValue&() const { return Val; }
 
   /// If implicit conversion to SDValue doesn't work, the get() method returns
   /// the SDValue.
   const SDValue &get() const { return Val; }
 
   /// This returns the SDNode that contains this Use.
   SDNode *getUser() { return User; }
 
-  /// Get the next SDUse in the use list.
-  SDUse *getNext() const { return Next; }
-
   /// Convenience function for get().getNode().
   SDNode *getNode() const { return Val.getNode(); }
   /// Convenience function for get().getResNo().
   unsigned getResNo() const { return Val.getResNo(); }
   /// Convenience function for get().getValueType().
   EVT getValueType() const { return Val.getValueType(); }
 
   /// Convenience function for get().operator==
private:
   /// given value, and add it to the new value's node's use list.
   inline void set(const SDValue &V);
   /// Like set, but only supports initializing a newly-allocated
   /// SDUse with a non-null value.
   inline void setInitial(const SDValue &V);
   /// Like set, but only sets the Node portion of the value,
   /// leaving the ResNo portion unmodified.
   inline void setNode(SDNode *N);
-
-  void addToList(SDUse **List) {
-    Next = *List;
-    if (Next) Next->Prev = &Next;
-    Prev = List;
-    *List = this;
-  }
-
-  void removeFromList() {
-    *Prev = Next;
-    if (Next) Next->Prev = Prev;
-  }
 };
 
 /// simplify_type specializations - Allow casting operators to work directly on
 /// SDValues as if they were SDNode*'s.
 template<> struct simplify_type<SDUse> {
   using SimpleType = SDNode *;
 
   static SimpleType getSimplifiedValue(SDUse &Val) {
private:
 
   /// The values that are used by this operation.
   SDUse *OperandList = nullptr;
 
   /// The types of the values this node defines.  SDNode's may
   /// define multiple values simultaneously.
   const EVT *ValueList;
 
-  /// List of uses for this SDNode.
+  /// Lists of uses for each value of this SDNode.
+  SmallVector<SDUse *> ResNoToUseList;
+  /// List of all uses. Duplicates info from ResNoToUseList but is easier
+  /// to iterate over so using it gives better performance in cases where
+  /// the whole use list is needed.
   SDUse *UseList = nullptr;
 
   /// The number of entries in the Operand/Value list.
   unsigned short NumOperands = 0;
   unsigned short NumValues;
 
   // The ordering of the SDNodes. It roughly corresponds to the ordering of the
   // original LLVM instructions.
#include "llvm/IR/ConstrainedOps.def"
   const DebugLoc &getDebugLoc() const { return debugLoc; }
 
   /// Set source location info.  Try to avoid this, putting
   /// it in the constructor is preferable.
   void setDebugLoc(DebugLoc dl) { debugLoc = std::move(dl); }
 
   /// This class provides iterator support for SDUse
   /// operands that use a specific SDNode.
-  class use_iterator {
+  template <bool NeedAllUses> class use_iterator_template {
     friend class SDNode;
 
     SDUse *Op = nullptr;
 
-    explicit use_iterator(SDUse *op) : Op(op) {}
+    explicit use_iterator_template(SDUse *Op) : Op(Op) {}
 
   public:
     using iterator_category = std::forward_iterator_tag;
     using value_type = SDUse;
     using difference_type = std::ptrdiff_t;
     using pointer = value_type *;
     using reference = value_type &;
 
-    use_iterator() = default;
-    use_iterator(const use_iterator &I) = default;
+    use_iterator_template() = default;
+    use_iterator_template(const use_iterator_template &I) = default;
 
-    bool operator==(const use_iterator &x) const { return Op == x.Op; }
-    bool operator!=(const use_iterator &x) const {
+    template <bool Param>
+    bool operator==(const use_iterator_template<Param> &x) const {
+      return Op == x.Op;
+    }
+    template <bool Param>
+    bool operator!=(const use_iterator_template<Param> &x) const {
       return !operator==(x);
     }
 
     /// 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
+    use_iterator_template &operator++() { // Preincrement
       assert(Op && "Cannot increment end iterator!");
-      Op = Op->getNext();
+      Op = (NeedAllUses ? Op->AllUsesNext : Op->ResNoUsesNext);
       return *this;
     }
 
-    use_iterator operator++(int) {        // Postincrement
-      use_iterator tmp = *this; ++*this; return tmp;
+    use_iterator_template operator++(int) { // Postincrement
+      use_iterator_template tmp = *this;
+      ++*this;
+      return tmp;
     }
 
     /// Retrieve a pointer to the current user node.
     SDNode *operator*() const {
       assert(Op && "Cannot dereference end iterator!");
       return Op->getUser();
     }
 
     SDNode *operator->() const { return operator*(); }
 
     SDUse &getUse() const { return *Op; }
 
     /// Retrieve the operand # of this use in its user.
     unsigned getOperandNo() const {
       assert(Op && "Cannot dereference end iterator!");
       return (unsigned)(Op - Op->getUser()->OperandList);
     }
   };
 
+  using use_iterator = use_iterator_template<true>;
+  using use_per_resno_iterator = use_iterator_template<false>;
+
   /// Provide iteration support to walk over all uses of an SDNode.
-  use_iterator use_begin() const {
-    return use_iterator(UseList);
-  }
+  use_iterator use_begin() const { return use_iterator(UseList); }
 
   static use_iterator use_end() { return use_iterator(nullptr); }
 
+#define LLVM_SDNODE_CHECK_USELIST_MAP_SIZE()                                   \
+  assert(ResNoToUseList.size() == NumValues &&                                 \
+         "ResNo count in UseList map does not match NumValues");
+
+public:
+  /// Provide iteration support to walk over all uses of an SDNode.
+  use_per_resno_iterator use_per_resno_begin(unsigned ResNo) const {
+    LLVM_SDNODE_CHECK_USELIST_MAP_SIZE();
+    assert(ResNo < NumValues && "ResNo exceeds NumValues");
+    return use_per_resno_iterator(ResNoToUseList[ResNo]);
+  }
+
+  use_per_resno_iterator use_per_resno_end(unsigned ResNo) const {
+    LLVM_SDNODE_CHECK_USELIST_MAP_SIZE();
+    assert(ResNo < NumValues && "ResNo exceeds NumValues");
+    return use_per_resno_iterator(nullptr);
+  }
+
   inline iterator_range<use_iterator> uses() {
+    LLVM_SDNODE_CHECK_USELIST_MAP_SIZE();
     return make_range(use_begin(), use_end());
   }
   inline iterator_range<use_iterator> uses() const {
+    LLVM_SDNODE_CHECK_USELIST_MAP_SIZE();
     return make_range(use_begin(), use_end());
   }
 
+  /// This method should only be used by the SDUse class.
+  void addUse(SDUse &U) {
+    LLVM_SDNODE_CHECK_USELIST_MAP_SIZE();
+    assert(U.getResNo() < NumValues && "ResNo exceeds NumValues");
+
+    SDUse **ResNoUsesList = &ResNoToUseList[U.getResNo()];
+    U.ResNoUsesNext = *ResNoUsesList;
+    if (U.ResNoUsesNext)
+      U.ResNoUsesNext->ResNoUsesPrev = &U.ResNoUsesNext;
+    U.ResNoUsesPrev = ResNoUsesList;
+    *ResNoUsesList = &U;
+
+    SDUse **AllUsesList = &UseList;
+    U.AllUsesNext = *AllUsesList;
+    if (U.AllUsesNext)
+      U.AllUsesNext->AllUsesPrev = &U.AllUsesNext;
+    U.AllUsesPrev = AllUsesList;
+    *AllUsesList = &U;
+  }
+
+  /// This method should only be used by the SDUse class.
+  void removeUse(SDUse &U) {
+    LLVM_SDNODE_CHECK_USELIST_MAP_SIZE();
+
+    *U.ResNoUsesPrev = U.ResNoUsesNext;
+    if (U.ResNoUsesNext)
+      U.ResNoUsesNext->ResNoUsesPrev = U.ResNoUsesPrev;
+
+    *U.AllUsesPrev = U.AllUsesNext;
+    if (U.AllUsesNext)
+      U.AllUsesNext->AllUsesPrev = U.AllUsesPrev;
+  }
+
+  /// To be used from MorphNodeTo when changing NumValues
+  /// leads to ResNoToUseList remapping.
+  void remapUses() {
+    std::vector<SDUse *> AllUses;
+    for (auto UI = use_begin(), UE = use_end(); UI != UE; ++UI) {
+      AllUses.emplace_back(&UI.getUse());
+    }
+
+    UseList = nullptr;
+    ResNoToUseList = SmallVector<SDUse *>(NumValues, nullptr);
+    for (auto it = AllUses.rbegin(); it != AllUses.rend(); ++it)
+      if ((*it)->getNode())
+        addUse(**it);
+  }
+
+#undef LLVM_SDNODE_CHECK_USELIST_MAP_SIZE
+
   /// 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;
 
   /// 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;
 
#undef LLVM_SDNODE_CHECK_USELIST_MAP_SIZE
   /// that appear multiple times wherever they are used.
   ///
   void dumprWithDepth(const SelectionDAG *G = nullptr,
                       unsigned depth = 100) const;
 
   /// Gather unique data for the node.
   void Profile(FoldingSetNodeID &ID) const;
 
-  /// This method should only be used by the SDUse class.
-  void addUse(SDUse &U) { U.addToList(&UseList); }
-
 protected:
   static SDVTList getSDVTList(EVT VT) {
     SDVTList Ret = { getValueTypeList(VT), 1 };
     return Ret;
   }
 
   /// Create an SDNode.
   ///
   /// SDNodes are created without any operands, and never own the operand
   /// storage. To add operands, see SelectionDAG::createOperands.
   SDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs)
-      : NodeType(Opc), ValueList(VTs.VTs), NumValues(VTs.NumVTs),
-        IROrder(Order), debugLoc(std::move(dl)) {
+      : NodeType(Opc), ValueList(VTs.VTs), ResNoToUseList(VTs.NumVTs, nullptr),
+        NumValues(VTs.NumVTs), IROrder(Order), debugLoc(std::move(dl)) {
     memset(&RawSDNodeBits, 0, sizeof(RawSDNodeBits));
     assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
     assert(NumValues == VTs.NumVTs &&
            "NumValues wasn't wide enough for its operands!");
   }
 
   /// Release the operands and set this node to have zero operands.
   void DropOperands();

 
 inline void SDValue::dumpr(const SelectionDAG *G) const {
   return Node->dumpr(G);
 }
 
 // Define inline functions from the SDUse class.
 
 inline void SDUse::set(const SDValue &V) {
-  if (Val.getNode()) removeFromList();
+  if (Val.getNode())
+    Val.getNode()->removeUse(*this);
   Val = V;
   if (V.getNode())
     V->addUse(*this);
 }
 
 inline void SDUse::setInitial(const SDValue &V) {
   Val = V;
   V->addUse(*this);
 }
 
 inline void SDUse::setNode(SDNode *N) {
-  if (Val.getNode()) removeFromList();
+  if (Val.getNode())
+    Val.getNode()->removeUse(*this);
   Val.setNode(N);
   if (N) N->addUse(*this);
 }
 
 /// 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.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

 // transformation. Returns true if extension are possible and the above
 // mentioned transformation is profitable.
 static bool ExtendUsesToFormExtLoad(EVT VT, SDNode *N, SDValue N0,
                                     unsigned ExtOpc,
                                     SmallVectorImpl<SDNode *> &ExtendNodes,
                                     const TargetLowering &TLI) {
   bool HasCopyToRegUses = false;
   bool isTruncFree = TLI.isTruncateFree(VT, N0.getValueType());
-  for (SDNode::use_iterator UI = N0->use_begin(), UE = N0->use_end(); UI != UE;
-       ++UI) {
+  for (auto UI = N0->use_per_resno_begin(N0.getResNo()),
+            UE = N0->use_per_resno_end(N0.getResNo());
+       UI != UE; ++UI) {
     SDNode *User = *UI;
     if (User == N)
       continue;
-    if (UI.getUse().getResNo() != N0.getResNo())
-      continue;
     // FIXME: Only extend SETCC N, N and SETCC N, c for now.
     if (ExtOpc != ISD::ANY_EXTEND && User->getOpcode() == ISD::SETCC) {
       ISD::CondCode CC = cast<CondCodeSDNode>(User->getOperand(2))->get();
       if (ExtOpc == ISD::ZERO_EXTEND && ISD::isSignedIntSetCC(CC))
         // Sign bits will be lost after a zext.
         return false;
       bool Add = false;
       for (unsigned i = 0; i != 2; ++i) {
if (!isTruncFree)
       return false;
     // Remember if this value is live-out.
     if (User->getOpcode() == ISD::CopyToReg)
       HasCopyToRegUses = true;
   }
 
   if (HasCopyToRegUses) {
     bool BothLiveOut = false;
-    for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
+    for (auto UI = N->use_per_resno_begin(0), UE = N->use_per_resno_end(0);
          UI != UE; ++UI) {
-      SDUse &Use = UI.getUse();
-      if (Use.getResNo() == 0 && Use.getUser()->getOpcode() == ISD::CopyToReg) {
+      if (UI.getUse().getUser()->getOpcode() == ISD::CopyToReg) {
         BothLiveOut = true;
         break;
       }
     }
     if (BothLiveOut)
       // Both unextended and extended values are live out. There had better be
       // a good reason for the transformation.
       return ExtendNodes.size();
if (N0.hasOneUse() && TLI.isOperationLegalOrCustom(ISD::SETCC, VT) &&
         if (!(ISD::isNON_EXTLoad(V.getNode()) &&
               ISD::isUNINDEXEDLoad(V.getNode()) &&
               cast<LoadSDNode>(V)->isSimple() &&
               TLI.isLoadExtLegal(LoadOpcode, VT, V.getValueType())))
           return false;
 
         // Non-chain users of this value must either be the setcc in this
         // sequence or extends that can be folded into the new {z/s}ext-load.
-        for (SDNode::use_iterator UI = V->use_begin(), UE = V->use_end();
+        for (auto UI = V->use_per_resno_begin(0), UE = V->use_per_resno_end(0);
              UI != UE; ++UI) {
           // Skip uses of the chain and the setcc.
           SDNode *User = *UI;
-          if (UI.getUse().getResNo() != 0 || User == N0.getNode())
+          if (User == N0.getNode())
             continue;
           // Extra users must have exactly the same cast we are about to create.
           // TODO: This restriction could be eased if ExtendUsesToFormExtLoad()
           //       is enhanced similarly.
           if (User->getOpcode() != ExtOpcode || User->getValueType(0) != VT)
             return false;
         }
         return true;
bool DAGCombiner::SliceUpLoad(SDNode *N) {
   // In that case, we will just abort the transformation.
   APInt UsedBits(LD->getValueSizeInBits(0), 0);
 
   SmallVector<LoadedSlice, 4> LoadedSlices;
 
   // Check if this load is used as several smaller chunks of bits.
   // Basically, look for uses in trunc or trunc(lshr) and record a new chain
   // of computation for each trunc.
-  for (SDNode::use_iterator UI = LD->use_begin(), UIEnd = LD->use_end();
+  // Iterate over uses of 0 value only to skip the uses of the chain.
+  for (auto UI = LD->use_per_resno_begin(0), UIEnd = LD->use_per_resno_end(0);
        UI != UIEnd; ++UI) {
-    // Skip the uses of the chain.
-    if (UI.getUse().getResNo() != 0)
-      continue;
-
     SDNode *User = *UI;
     unsigned Shift = 0;
 
     // Check if this is a trunc(lshr).
     if (User->getOpcode() == ISD::SRL && User->hasOneUse() &&
         isa<ConstantSDNode>(User->getOperand(1))) {
       Shift = User->getConstantOperandVal(1);
       User = *User->use_begin();

llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp

for (unsigned i = 0, e = Node.getNumValues(); i != e; ++i) {
       bool Failed = false;
       // Don't create a value in map.
       auto ResId = ValueToIdMap.lookup(Res);
 
       unsigned Mapped = 0;
       if (ResId && (ReplacedValues.find(ResId) != ReplacedValues.end())) {
         Mapped |= 1;
         // Check that remapped values are only used by nodes marked NewNode.
-        for (SDNode::use_iterator UI = Node.use_begin(), UE = Node.use_end();
+        for (auto UI = Node.use_per_resno_begin(i),
+                  UE = Node.use_per_resno_end(i);
              UI != UE; ++UI)
-          if (UI.getUse().getResNo() == i)
-            assert(UI->getNodeId() == NewNode &&
-                   "Remapped value has non-trivial use!");
 
         // Check that the final result of applying ReplacedValues is not
         // marked NewNode.
         auto NewValId = ReplacedValues[ResId];
         auto I = ReplacedValues.find(NewValId);
         while (I != ReplacedValues.end()) {
           NewValId = I->second;
           I = ReplacedValues.find(NewValId);

llvm/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
   SDNode *Base = Node;
 
   if (hasTiedInput(Base))
     return;
 
   // This algorithm requires a reasonably low use count before finding a match
   // to avoid uselessly blowing up compile time in large blocks.
   unsigned UseCount = 0;
-  for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
+  unsigned ChResNo = Chain.getResNo();
+  for (auto I = Chain->use_per_resno_begin(ChResNo),
+            E = Chain->use_per_resno_end(ChResNo);
        I != E && UseCount < 100; ++I, ++UseCount) {
-    if (I.getUse().getResNo() != Chain.getResNo())
-      continue;
-
     SDNode *User = *I;
     if (User == Node || !Visited.insert(User).second)
       continue;
     int64_t Offset1, Offset2;
     if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
         Offset1 == Offset2 ||
         hasTiedInput(User)) {
       // FIXME: Should be ok if they addresses are identical. But earlier

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

void SelectionDAG::clear() {
   CSEMap.clear();
 
   ExtendedValueTypeNodes.clear();
   ExternalSymbols.clear();
   TargetExternalSymbols.clear();
   MCSymbols.clear();
   SDCallSiteDbgInfo.clear();
   std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
-            static_cast<CondCodeSDNode*>(nullptr));
+            static_cast<CondCodeSDNode *>(nullptr));
   std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
-            static_cast<SDNode*>(nullptr));
-
+            static_cast<SDNode *>(nullptr));
+  std::fill(EntryNode.ResNoToUseList.begin(), EntryNode.ResNoToUseList.end(),
+            static_cast<SDUse *>(nullptr));
   EntryNode.UseList = nullptr;
+
   InsertNode(&EntryNode);
   Root = getEntryNode();
   DbgInfo->clear();
 }
 
 SDValue SelectionDAG::getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT) {
   return VT.bitsGT(Op.getValueType())
              ? getNode(ISD::FP_EXTEND, DL, VT, Op)
SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
 
   if (!RemoveNodeFromCSEMaps(N))
     IP = nullptr;
 
   // Start the morphing.
   N->NodeType = Opc;
   N->ValueList = VTs.VTs;
   N->NumValues = VTs.NumVTs;
+  N->remapUses();
 
   // Clear the operands list, updating used nodes to remove this from their
   // use list.  Keep track of any operands that become dead as a result.
   SmallPtrSet<SDNode*, 16> DeadNodeSet;
   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
     SDUse &Use = *I++;
     SDNode *Used = Use.getNode();
     Use.set(SDValue());
void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
 
   // Read up all the uses and make records of them. This helps
   // processing new uses that are introduced during the
   // replacement process.
   SmallVector<UseMemo, 4> Uses;
   for (unsigned i = 0; i != Num; ++i) {
     unsigned FromResNo = From[i].getResNo();
     SDNode *FromNode = From[i].getNode();
-    for (SDNode::use_iterator UI = FromNode->use_begin(),
-         E = FromNode->use_end(); UI != E; ++UI) {
-      SDUse &Use = UI.getUse();
-      if (Use.getResNo() == FromResNo) {
-        UseMemo Memo = { *UI, i, &Use };
-        Uses.push_back(Memo);
-      }
-    }
-  }
+    for (auto UI = FromNode->use_per_resno_begin(FromResNo),
+              E = FromNode->use_per_resno_end(FromResNo);
+         UI != E; ++UI) {
+      UseMemo Memo = {*UI, i, &UI.getUse()};
 
   // Sort the uses, so that all the uses from a given User are together.
   llvm::sort(Uses);
   RAUOVWUpdateListener Listener(*this, Uses);
 
   for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
        UseIndex != UseIndexEnd; ) {
     // We know that this user uses some value of From.  If it is the right

 }
 
 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
 /// indicated value.  This method ignores uses of other values defined by this
 /// operation.
 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
   assert(Value < getNumValues() && "Bad value!");
 
-  // TODO: Only iterate over uses of a given value of the node
-  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
-    if (UI.getUse().getResNo() == Value) {
-      if (NUses == 0)
-        return false;
-      --NUses;
-    }
-  }
+  for (auto UI = use_per_resno_begin(Value), UE = use_per_resno_end(Value);
+       UI != UE; ++UI) {
 
   // Found exactly the right number of uses?
   return NUses == 0;
 }
 
 /// hasAnyUseOfValue - Return true if there are any use of the indicated
 /// value. This method ignores uses of other values defined by this operation.
 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
   assert(Value < getNumValues() && "Bad value!");
-
-  for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
-    if (UI.getUse().getResNo() == Value)
-      return true;
-
-  return false;
+  return (ResNoToUseList[Value] != nullptr);
 }
 
 /// isOnlyUserOf - Return true if this node is the only use of N.
 bool SDNode::isOnlyUserOf(const SDNode *N) const {
   bool Seen = false;
   for (const SDNode *User : N->uses()) {
     if (User == this)
       Seen = true;
case ISD::FMAXNUM: {
 
     return getConstantFP(NeutralAF, DL, VT);
   }
   }
 }
 
 #ifndef NDEBUG
 static void checkForCyclesHelper(const SDNode *N,
-                                 SmallPtrSetImpl<const SDNode*> &Visited,
-                                 SmallPtrSetImpl<const SDNode*> &Checked,
+                                 SmallPtrSetImpl<const SDNode *> &Visited,
+                                 SmallPtrSetImpl<const SDNode *> &Checked,
                                  const llvm::SelectionDAG *DAG) {
   // If this node has already been checked, don't check it again.
   if (Checked.count(N))
     return;
 
   // If a node has already been visited on this depth-first walk, reject it as
   // a cycle.
   if (!Visited.insert(N).second) {

llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

if (e != InOps.size())
     Ops.push_back(InOps.back());
 }
 
 /// findGlueUse - Return use of MVT::Glue value produced by the specified
 /// SDNode.
 ///
 static SDNode *findGlueUse(SDNode *N) {
   unsigned FlagResNo = N->getNumValues()-1;
-  for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
-    SDUse &Use = I.getUse();
-    if (Use.getResNo() == FlagResNo)
-      return Use.getUser();
-  }
+  auto UseIt = N->use_per_resno_begin(FlagResNo);
+
+  if (UseIt != N->use_end())
+    return UseIt.getUse().getUser();
+
   return nullptr;
 }
 
 /// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
 /// beyond "ImmedUse".  We may ignore chains as they are checked separately.
 static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
                           bool IgnoreChains) {
   SmallPtrSet<const SDNode *, 16> Visited;

llvm/lib/Target/AMDGPU/AMDGPUISelDAGToDAG.cpp

 
 void AMDGPUDAGToDAGISel::SelectUADDO_USUBO(SDNode *N) {
   // The name of the opcodes are misleading. v_add_i32/v_sub_i32 have unsigned
   // carry out despite the _i32 name. These were renamed in VI to _U32.
   // FIXME: We should probably rename the opcodes here.
   bool IsAdd = N->getOpcode() == ISD::UADDO;
   bool IsVALU = N->isDivergent();
 
-  for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;
-       ++UI)
-    if (UI.getUse().getResNo() == 1) {
-      if ((IsAdd && (UI->getOpcode() != ISD::ADDCARRY)) ||
-          (!IsAdd && (UI->getOpcode() != ISD::SUBCARRY))) {
-        IsVALU = true;
-        break;
-      }
-    }
+  for (auto UI = N->use_per_resno_begin(1), E = N->use_per_resno_end(1);
+       UI != E; ++UI) {
 
   if (IsVALU) {
     unsigned Opc = IsAdd ? AMDGPU::V_ADD_CO_U32_e64 : AMDGPU::V_SUB_CO_U32_e64;
 
     CurDAG->SelectNodeTo(
         N, Opc, N->getVTList(),
         {N->getOperand(0), N->getOperand(1),
          CurDAG->getTargetConstant(0, {}, MVT::i1) /*clamp bit*/});

llvm/lib/Target/AMDGPU/SIISelLowering.cpp

default:
     break;
   }
 }
 
 /// Helper function for LowerBRCOND
 static SDNode *findUser(SDValue Value, unsigned Opcode) {
 
   SDNode *Parent = Value.getNode();
-  for (SDNode::use_iterator I = Parent->use_begin(), E = Parent->use_end();
+  unsigned ResNo = Value.getResNo();
+  for (auto I = Parent->use_per_resno_begin(ResNo),
+            E = Parent->use_per_resno_end(ResNo);
        I != E; ++I) {
-
-    if (I.getUse().get() != Value)
-      continue;
-
     if (I->getOpcode() == Opcode)
       return *I;
   }
   return nullptr;
 }
 
 unsigned SITargetLowering::isCFIntrinsic(const SDNode *Intr) const {
   if (Intr->getOpcode() == ISD::INTRINSIC_W_CHAIN) {
SDNode *SITargetLowering::adjustWritemask(MachineSDNode *&Node,
 
   unsigned OldBitsSet = countPopulation(OldDmask);
   // Work out which is the TFE/LWE lane if that is enabled.
   if (UsesTFC) {
     TFCLane = OldBitsSet;
   }
 
   // Try to figure out the used register components
-  for (SDNode::use_iterator I = Node->use_begin(), E = Node->use_end();
-       I != E; ++I) {
-
-    // Don't look at users of the chain.
-    if (I.getUse().getResNo() != 0)
-      continue;
-
+  for (auto I = Node->use_per_resno_begin(0), E = Node->use_per_resno_end(0);
+       I != E; ++I) {
     // Abort if we can't understand the usage
     if (!I->isMachineOpcode() ||
         I->getMachineOpcode() != TargetOpcode::EXTRACT_SUBREG)
       return Node;
 
     // Lane means which subreg of %vgpra_vgprb_vgprc_vgprd is used.
     // Note that subregs are packed, i.e. Lane==0 is the first bit set
     // in OldDmask, so it can be any of X,Y,Z,W; Lane==1 is the second bit

llvm/lib/Target/ARM/ARMISelLowering.cpp

static SDValue CombineBaseUpdate(SDNode *N,
   const unsigned AddrOpIdx = ((isIntrinsic || isStore) ? 2 : 1);
   BaseUpdateTarget Target = {N, isIntrinsic, isStore, AddrOpIdx};
 
   SDValue Addr = N->getOperand(AddrOpIdx);
 
   SmallVector<BaseUpdateUser, 8> BaseUpdates;
 
   // Search for a use of the address operand that is an increment.
-  for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
-         UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
+  for (auto UI = Addr.getNode()->use_per_resno_begin(Addr.getResNo()),
+            UE = Addr.getNode()->use_per_resno_end(Addr.getResNo());
+       UI != UE; ++UI) {
     SDNode *User = *UI;
-    if (UI.getUse().getResNo() != Addr.getResNo() ||
-        User->getNumOperands() != 2)
+    if (User->getNumOperands() != 2)
       continue;
 
     SDValue Inc = User->getOperand(UI.getOperandNo() == 1 ? 0 : 1);
     unsigned ConstInc =
         getPointerConstIncrement(User->getOpcode(), Addr, Inc, DCI.DAG);
 
     if (ConstInc || User->getOpcode() == ISD::ADD)
       BaseUpdates.push_back({User, Inc, ConstInc});
   }
 
   // If the address is a constant pointer increment itself, find
   // another constant increment that has the same base operand
   SDValue Base;
   SDValue CInc;
   if (findPointerConstIncrement(Addr.getNode(), &Base, &CInc)) {
     unsigned Offset =
         getPointerConstIncrement(Addr->getOpcode(), Base, CInc, DCI.DAG);
-    for (SDNode::use_iterator UI = Base->use_begin(), UE = Base->use_end();
+
+    unsigned BaseResNo = Base.getResNo();
+    for (auto UI = Base->use_per_resno_begin(BaseResNo),
+              UE = Base->use_per_resno_end(BaseResNo);
          UI != UE; ++UI) {
 
       SDNode *User = *UI;
-      if (UI.getUse().getResNo() != Base.getResNo() || User == Addr.getNode() ||
-          User->getNumOperands() != 2)
+      if (User == Addr.getNode() || User->getNumOperands() != 2)
         continue;
 
       SDValue UserInc = User->getOperand(UI.getOperandNo() == 0 ? 1 : 0);
       unsigned UserOffset =
           getPointerConstIncrement(User->getOpcode(), Base, UserInc, DCI.DAG);
 
       if (!UserOffset || UserOffset <= Offset)
         continue;
static SDValue PerformMVEVLDCombine(SDNode *N,
   if (IntNo == Intrinsic::arm_mve_vst2q &&
       cast<ConstantSDNode>(N->getOperand(5))->getZExtValue() != 1)
     return SDValue();
   if (IntNo == Intrinsic::arm_mve_vst4q &&
       cast<ConstantSDNode>(N->getOperand(7))->getZExtValue() != 3)
     return SDValue();
 
   // Search for a use of the address operand that is an increment.
-  for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
-                            UE = Addr.getNode()->use_end();
+  for (auto UI = Addr.getNode()->use_per_resno_begin(Addr.getResNo()),
+            UE = Addr.getNode()->use_per_resno_end(Addr.getResNo());
        UI != UE; ++UI) {
     SDNode *User = *UI;
-    if (User->getOpcode() != ISD::ADD ||
-        UI.getUse().getResNo() != Addr.getResNo())
+    if (User->getOpcode() != ISD::ADD)
       continue;
 
     // Check that the add is independent of the load/store.  Otherwise, folding
     // it would create a cycle. We can avoid searching through Addr as it's a
     // predecessor to both.
     SmallPtrSet<const SDNode *, 32> Visited;
     SmallVector<const SDNode *, 16> Worklist;
     Visited.insert(Addr.getNode());

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

static bool usePartialVectorLoads(SDNode *N, const PPCSubtarget& ST) {
   default:
     return false;
   }
 
   SDValue LoadedVal(N, 0);
   if (!LoadedVal.hasOneUse())
     return false;
 
-  for (SDNode::use_iterator UI = LD->use_begin(), UE = LD->use_end();
+  for (auto UI = LD->use_per_resno_begin(0), UE = LD->use_per_resno_end(0);
        UI != UE; ++UI)
-    if (UI.getUse().get().getResNo() == 0 &&
-        UI->getOpcode() != ISD::SCALAR_TO_VECTOR &&
+    if (UI->getOpcode() != ISD::SCALAR_TO_VECTOR &&
         UI->getOpcode() != PPCISD::SCALAR_TO_VECTOR_PERMUTED)
       return false;
 
   return true;
 }
 
 /// getPreIndexedAddressParts - returns true by value, base pointer and
 /// offset pointer and addressing mode by reference if the node's address
if (Origin->getOpcode() != ISD::LOAD)
     return true;
 
   // If there is no LXSIBZX/LXSIHZX, like Power8,
   // prefer direct move if the memory size is 1 or 2 bytes.
   MachineMemOperand *MMO = cast<LoadSDNode>(Origin)->getMemOperand();
   if (!Subtarget.hasP9Vector() && MMO->getSize() <= 2)
     return true;
 
-  for (SDNode::use_iterator UI = Origin->use_begin(),
-                            UE = Origin->use_end();
-       UI != UE; ++UI) {
-
-    // Only look at the users of the loaded value.
-    if (UI.getUse().get().getResNo() != 0)
-      continue;
-
+  for (auto UI = Origin->use_per_resno_begin(0),
+            UE = Origin->use_per_resno_end(0);
+       UI != UE; ++UI) {
     if (UI->getOpcode() != ISD::SINT_TO_FP &&
         UI->getOpcode() != ISD::UINT_TO_FP &&
         UI->getOpcode() != ISD::STRICT_SINT_TO_FP &&
         UI->getOpcode() != ISD::STRICT_UINT_TO_FP)
       return true;
   }
 
   return false;
SDValue PPCTargetLowering::combineVReverseMemOP(ShuffleVectorSDNode *SVN,
 
   if(!IsElementReverse(SVN))
     return SDValue();
 
   if (LSBase->getOpcode() == ISD::LOAD) {
     // If the load return value 0 has more than one user except the
     // shufflevector instruction, it is not profitable to replace the
     // shufflevector with a reverse load.
-    for (SDNode::use_iterator UI = LSBase->use_begin(), UE = LSBase->use_end();
+    for (auto UI = LSBase->use_per_resno_begin(0),
+              UE = LSBase->use_per_resno_end(0);
          UI != UE; ++UI)
-      if (UI.getUse().getResNo() == 0 && UI->getOpcode() != ISD::VECTOR_SHUFFLE)
+      if (UI->getOpcode() != ISD::VECTOR_SHUFFLE)
         return SDValue();
 
     SDLoc dl(LSBase);
     SDValue LoadOps[] = {LSBase->getChain(), LSBase->getBasePtr()};
     return DAG.getMemIntrinsicNode(
         PPCISD::LOAD_VEC_BE, dl, DAG.getVTList(VT, MVT::Other), LoadOps,
         LSBase->getMemoryVT(), LSBase->getMemOperand());
   }
auto ReplaceTwoFloatLoad = [&]() {
       //    t17: i32 = truncate t16
       //  t18: f32 = bitcast t17
       //    t19: i32 = truncate t13
       //  t20: f32 = bitcast t19
 
       if (!LD->hasNUsesOfValue(2, 0))
         return false;
 
-      auto UI = LD->use_begin();
-      while (UI.getUse().getResNo() != 0) ++UI;
+      auto UI = LD->use_per_resno_begin(0);
       SDNode *Trunc = *UI++;
-      while (UI.getUse().getResNo() != 0) ++UI;
       SDNode *RightShift = *UI;
       if (Trunc->getOpcode() != ISD::TRUNCATE)
         std::swap(Trunc, RightShift);
 
       if (Trunc->getOpcode() != ISD::TRUNCATE ||
           Trunc->getValueType(0) != MVT::i32 ||
           !Trunc->hasOneUse())
         return false;

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

X86::CondCode X86DAGToDAGISel::getCondFromNode(SDNode *N) const {
 
   return static_cast<X86::CondCode>(N->getConstantOperandVal(CondNo));
 }
 
 /// Test whether the given X86ISD::CMP node has any users that use a flag
 /// other than ZF.
 bool X86DAGToDAGISel::onlyUsesZeroFlag(SDValue Flags) const {
   // Examine each user of the node.
-  for (SDNode::use_iterator UI = Flags->use_begin(), UE = Flags->use_end();
-         UI != UE; ++UI) {
-    // Only check things that use the flags.
-    if (UI.getUse().getResNo() != Flags.getResNo())
-      continue;
+  for (auto UI = Flags->use_per_resno_begin(Flags.getResNo()),
+            UE = Flags->use_per_resno_end(Flags.getResNo());
+       UI != UE; ++UI) {
     // Only examine CopyToReg uses that copy to EFLAGS.
     if (UI->getOpcode() != ISD::CopyToReg ||
         cast<RegisterSDNode>(UI->getOperand(1))->getReg() != X86::EFLAGS)
       return false;
     // Examine each user of the CopyToReg use.
-    for (SDNode::use_iterator FlagUI = UI->use_begin(),
-           FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) {
-      // Only examine the Flag result.
-      if (FlagUI.getUse().getResNo() != 1) continue;
+    for (auto FlagUI = UI->use_per_resno_begin(1),
+              FlagUE = UI->use_per_resno_end(1);
+         FlagUI != FlagUE; ++FlagUI) {
       // Anything unusual: assume conservatively.
       if (!FlagUI->isMachineOpcode()) return false;
       // Examine the condition code of the user.
       X86::CondCode CC = getCondFromNode(*FlagUI);
 
       switch (CC) {
       // Comparisons which only use the zero flag.
       case X86::COND_E: case X86::COND_NE:
         continue;
       // Anything else: assume conservatively.
       default:
         return false;
       }
     }
   }
   return true;
 }
 
 /// Test whether the given X86ISD::CMP node has any uses which require the SF
 /// flag to be accurate.
 bool X86DAGToDAGISel::hasNoSignFlagUses(SDValue Flags) const {
   // Examine each user of the node.
-  for (SDNode::use_iterator UI = Flags->use_begin(), UE = Flags->use_end();
-         UI != UE; ++UI) {
-    // Only check things that use the flags.
-    if (UI.getUse().getResNo() != Flags.getResNo())
-      continue;
+  for (auto UI = Flags->use_per_resno_begin(Flags.getResNo()),
+            UE = Flags->use_per_resno_end(Flags.getResNo());
+       UI != UE; ++UI) {
     // Only examine CopyToReg uses that copy to EFLAGS.
     if (UI->getOpcode() != ISD::CopyToReg ||
         cast<RegisterSDNode>(UI->getOperand(1))->getReg() != X86::EFLAGS)
       return false;
     // Examine each user of the CopyToReg use.
-    for (SDNode::use_iterator FlagUI = UI->use_begin(),
-           FlagUE = UI->use_end(); FlagUI != FlagUE; ++FlagUI) {
-      // Only examine the Flag result.
-      if (FlagUI.getUse().getResNo() != 1) continue;
+    for (auto FlagUI = UI->use_per_resno_begin(1),
+              FlagUE = UI->use_per_resno_end(1);
+         FlagUI != FlagUE; ++FlagUI) {
       // Anything unusual: assume conservatively.
       if (!FlagUI->isMachineOpcode()) return false;
       // Examine the condition code of the user.
       X86::CondCode CC = getCondFromNode(*FlagUI);
 
       switch (CC) {
       // Comparisons which don't examine the SF flag.
       case X86::COND_A: case X86::COND_AE:
static bool mayUseCarryFlag(X86::CondCode CC) {
   // Anything else: assume conservatively.
   default:
     return true;
   }
 }
 
 /// Test whether the given node which sets flags has any uses which require the
 /// CF flag to be accurate.
- bool X86DAGToDAGISel::hasNoCarryFlagUses(SDValue Flags) const {
   // Examine each user of the node.
-  for (SDNode::use_iterator UI = Flags->use_begin(), UE = Flags->use_end();
-         UI != UE; ++UI) {
-    // Only check things that use the flags.
-    if (UI.getUse().getResNo() != Flags.getResNo())
-      continue;
-
+  for (auto UI = Flags->use_per_resno_begin(Flags.getResNo()),
+            UE = Flags->use_per_resno_end(Flags.getResNo());
+       UI != UE; ++UI) {
     unsigned UIOpc = UI->getOpcode();
 
     if (UIOpc == ISD::CopyToReg) {
       // Only examine CopyToReg uses that copy to EFLAGS.
       if (cast<RegisterSDNode>(UI->getOperand(1))->getReg() != X86::EFLAGS)
         return false;
+
       // Examine each user of the CopyToReg use.
-      for (SDNode::use_iterator FlagUI = UI->use_begin(), FlagUE = UI->use_end();
-           FlagUI != FlagUE; ++FlagUI) {
-        // Only examine the Flag result.
-        if (FlagUI.getUse().getResNo() != 1)
-          continue;
+      for (auto FlagUI = UI->use_per_resno_begin(1),
+                FlagUE = UI->use_per_resno_end(1);
+           FlagUI != FlagUE; ++FlagUI) {
         // Anything unusual: assume conservatively.
         if (!FlagUI->isMachineOpcode())
           return false;
         // Examine the condition code of the user.
         X86::CondCode CC = getCondFromNode(*FlagUI);
 
         if (mayUseCarryFlag(CC))
           return false;

llvm/lib/Target/X86/X86ISelLowering.cpp

if (BasePtr.getOpcode() == X86ISD::WrapperRIP)
     if (const auto *GA = dyn_cast<GlobalAddressSDNode>(BasePtr.getOperand(0)))
       return GA->getTargetFlags() != X86II::MO_GOTTPOFF;
 
   // If this is an (1) AVX vector load with (2) multiple uses and (3) all of
   // those uses are extracted directly into a store, then the extract + store
   // can be store-folded. Therefore, it's probably not worth splitting the load.
   EVT VT = Load->getValueType(0);
   if ((VT.is256BitVector() || VT.is512BitVector()) && !Load->hasOneUse()) {
-    for (auto UI = Load->use_begin(), UE = Load->use_end(); UI != UE; ++UI) {
-      // Skip uses of the chain value. Result 0 of the node is the load value.
-      if (UI.getUse().getResNo() != 0)
-        continue;
-
+    for (auto UI = Load->use_per_resno_begin(0),
+              UE = Load->use_per_resno_end(0);
+         UI != UE; ++UI) {
       // If this use is not an extract + store, it's probably worth splitting.
       if (UI->getOpcode() != ISD::EXTRACT_SUBVECTOR || !UI->hasOneUse() ||
           UI->use_begin()->getOpcode() != ISD::STORE)
         return true;
     }
     // All non-chain uses are extract + store.
     return false;
   }