4 files changed, 54 insertions, 2 deletions

diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index d55dd7f295..33ebd00720 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -63,6 +63,10 @@ enum CombineLevel {
   NoIllegalOperations // Combine may only create legal operations and types.
 };
 
+class SelectionDAG;
+void checkForCycles(const SDNode *N);
+void checkForCycles(const SelectionDAG *DAG);
+
 /// SelectionDAG class - This is used to represent a portion of an LLVM function
 /// in a low-level Data Dependence DAG representation suitable for instruction
 /// selection.  This DAG is constructed as the first step of instruction
@@ -204,7 +208,12 @@ public:
   const SDValue &setRoot(SDValue N) {
     assert((!N.getNode() || N.getValueType() == MVT::Other) &&
            "DAG root value is not a chain!");
-    return Root = N;
+    if (N.getNode())
+      checkForCycles(N.getNode());
+    Root = N;
+    if (N.getNode())
+      checkForCycles(this);
+    return Root;
   }
 
   /// Combine - This iterates over the nodes in the SelectionDAG, folding
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index 6a53155f1b..45a9d40719 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -44,6 +44,8 @@ template <typename T> struct DenseMapInfo;
 template <typename T> struct simplify_type;
 template <typename T> struct ilist_traits;
 
+void checkForCycles(const SDNode *N);
+  
 /// SDVTList - 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(...).
@@ -1363,6 +1365,7 @@ protected:
       OperandList[i].setUser(this);
       OperandList[i].setInitial(Ops[i]);
     }
+    checkForCycles(this);
   }
 
   /// This constructor adds no operands itself; operands can be
@@ -1379,6 +1382,7 @@ protected:
     Ops[0].setInitial(Op0);
     NumOperands = 1;
     OperandList = Ops;
+    checkForCycles(this);
   }
 
   /// InitOperands - Initialize the operands list of this with 2 operands.
@@ -1389,6 +1393,7 @@ protected:
     Ops[1].setInitial(Op1);
     NumOperands = 2;
     OperandList = Ops;
+    checkForCycles(this);
   }
 
   /// InitOperands - Initialize the operands list of this with 3 operands.
@@ -1402,6 +1407,7 @@ protected:
     Ops[2].setInitial(Op2);
     NumOperands = 3;
     OperandList = Ops;
+    checkForCycles(this);
   }
 
   /// InitOperands - Initialize the operands list of this with 4 operands.
@@ -1417,6 +1423,7 @@ protected:
     Ops[3].setInitial(Op3);
     NumOperands = 4;
     OperandList = Ops;
+    checkForCycles(this);
   }
 
   /// InitOperands - Initialize the operands list of this with N operands.
@@ -1427,6 +1434,7 @@ protected:
     }
     NumOperands = N;
     OperandList = Ops;
+    checkForCycles(this);
   }
 
   /// DropOperands - Release the operands and set this node to have
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index ad0e862c6b..67b6d5c47b 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -5172,6 +5172,7 @@ unsigned SelectionDAG::AssignTopologicalOrder() {
   // count of outstanding operands.
   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
     SDNode *N = I++;
+    checkForCycles(N);
     unsigned Degree = N->getNumOperands();
     if (Degree == 0) {
       // A node with no uses, add it to the result array immediately.
@@ -5191,6 +5192,7 @@ unsigned SelectionDAG::AssignTopologicalOrder() {
   // such that by the time the end is reached all nodes will be sorted.
   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
     SDNode *N = I;
+    checkForCycles(N);
     // N is in sorted position, so all its uses have one less operand
     // that needs to be sorted.
     for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
@@ -5216,7 +5218,7 @@ unsigned SelectionDAG::AssignTopologicalOrder() {
       SDNode *S = ++J;
       dbgs() << "Offending node:\n";
       S->dumprFull();
-      assert(I != SortedPos && "Overran sorted position");
+      assert(0 && "Overran sorted position");
     }
   }
 
@@ -6279,3 +6281,35 @@ bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
       return false;
   return true;
 }
+
+static void checkForCyclesHelper(const SDNode *N,
+                                 std::set<const SDNode *> &visited) {
+  if (visited.find(N) != visited.end()) {
+    dbgs() << "Offending node:\n";
+    N->dumprFull();
+    assert(0 && "Detected cycle in SelectionDAG");
+  }
+
+  std::set<const SDNode*>::iterator i;
+  bool inserted;
+
+  tie(i, inserted) = visited.insert(N);
+  assert(inserted && "Missed cycle");
+
+  for(unsigned i = 0; i < N->getNumOperands(); ++i) {
+    checkForCyclesHelper(N->getOperand(i).getNode(), visited);
+  }
+  visited.erase(i);
+}
+
+void llvm::checkForCycles(const llvm::SDNode *N) {
+#ifdef XDEBUG
+  assert(N && "Checking nonexistant SDNode");
+  std::set<const SDNode *> visited;
+  checkForCyclesHelper(N, visited);
+#endif
+}
+
+void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
+  checkForCycles(DAG->getRoot().getNode());
+}
diff --git a/lib/Target/X86/X86ISelDAGToDAG.cpp b/lib/Target/X86/X86ISelDAGToDAG.cpp
index 13f4030e12..01cad71977 100644
--- a/lib/Target/X86/X86ISelDAGToDAG.cpp
+++ b/lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -598,6 +598,7 @@ void X86DAGToDAGISel::PreprocessForRMW() {
     if (RModW) {
       MoveBelowTokenFactor(CurDAG, Load, SDValue(I, 0), Chain);
       ++NumLoadMoved;
+      checkForCycles(I);
     }
   }
 }