[SelectionDAG] Get rid of recursion in findNonImmUse

[mkazantsev]

Summary

The recursive implementation of findNonImmUse may overflow stack
on extremely long use chains. This patch replaces it with an equivalent
iterative implementation.

[mkazantsev]

Approved by @bogner by email.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

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();
   }
   return nullptr;
 }
 
 /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
-/// This function recursively traverses up the operand chain, ignoring
+/// This function iteratively traverses up the operand chain, ignoring
 /// certain nodes.
 static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
                           SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited,
                           bool IgnoreChains) {
   // The NodeID's are given uniques ID's where a node ID is guaranteed to be
   // greater than all of its (recursive) operands.  If we scan to a point where
   // 'use' is smaller than the node we're scanning for, then we know we will
   // never find it.
   //
   // The Use may be -1 (unassigned) if it is a newly allocated node.  This can
   // happen because we scan down to newly selected nodes in the case of glue
   // uses.
-  if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1))
-    return false;
+  std::vector<SDNode *> WorkList;
+  WorkList.push_back(Use);
+
+  while (!WorkList.empty()) {
+    Use = WorkList.back();
+    WorkList.pop_back();
+    if (Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)
+      continue;
 
     // Don't revisit nodes if we already scanned it and didn't fail, we know we
     // won't fail if we scan it again.
     if (!Visited.insert(Use).second)
-    return false;
+      continue;
 
     for (const SDValue &Op : Use->op_values()) {
       // Ignore chain uses, they are validated by HandleMergeInputChains.
       if (Op.getValueType() == MVT::Other && IgnoreChains)
         continue;
 
       SDNode *N = Op.getNode();
       if (N == Def) {
         if (Use == ImmedUse || Use == Root)
           continue;  // We are not looking for immediate use.
         assert(N != Root);
         return true;
       }
 
       // Traverse up the operand chain.
-    if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains))
-      return true;
+      WorkList.push_back(N);
+    }
   }
   return false;
 }
 
 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
 /// operand node N of U during instruction selection that starts at Root.
 bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
                                           SDNode *Root) const {