Index: lib/CodeGen/ScheduleDAG.cpp
===================================================================
--- lib/CodeGen/ScheduleDAG.cpp
+++ lib/CodeGen/ScheduleDAG.cpp
@@ -290,34 +290,68 @@
 /// ComputeHeight - Calculate the maximal path from the node to the entry.
 ///
 void SUnit::ComputeHeight() {
-  SmallVector<SUnit*, 8> WorkList;
-  WorkList.push_back(this);
-  do {
-    SUnit *Cur = WorkList.back();
+  if (Succs.empty()) {
+    Height = 0;
+    isHeightCurrent = true;
+    return;
+  }
 
-    bool Done = true;
-    unsigned MaxSuccHeight = 0;
-    for (SUnit::const_succ_iterator I = Cur->Succs.begin(),
-         E = Cur->Succs.end(); I != E; ++I) {
+  SmallVector<std::pair<SUnit *, SUnit::const_succ_iterator>, 8> Stack;
+#ifndef NDEBUG
+  SmallPtrSet<SUnit *, 8> Visited;
+  Visited.insert(this);
+#endif
+  Height = 0;
+  SUnit *Cur = this;
+  SUnit::const_succ_iterator I = Succs.begin();
+  for (;;) {
+    assert(!Cur->isHeightCurrent &&
+           "No need to compute the height once current!");
+
+    SUnit::const_succ_iterator E = Cur->Succs.end();
+    assert(I != E && "Got an end iterator into the stack!");
+
+    do {
       SUnit *SuccSU = I->getSUnit();
-      if (SuccSU->isHeightCurrent)
-        MaxSuccHeight = std::max(MaxSuccHeight,
-                                 SuccSU->Height + I->getLatency());
-      else {
-        Done = false;
-        WorkList.push_back(SuccSU);
+      assert(!Visited.count(SuccSU) && "Found a cycle!");
+
+      if (!SuccSU->isHeightCurrent) {
+        if (SuccSU->Succs.empty()) {
+          SuccSU->Height = 0;
+          SuccSU->isHeightCurrent = true;
+        } else {
+          // We have a successor without a current height.
+          // Push the current position onto the stack and process that
+          // successor.
+          Stack.push_back({Cur, I});
+          Cur = SuccSU;
+#ifndef NDEBUG
+          Visited.insert(Cur);
+#endif
+          I = Cur->Succs.begin();
+          E = Cur->Succs.end();
+          continue;
+        }
       }
-    }
 
-    if (Done) {
-      WorkList.pop_back();
-      if (MaxSuccHeight != Cur->Height) {
-        Cur->setHeightDirty();
-        Cur->Height = MaxSuccHeight;
-      }
-      Cur->isHeightCurrent = true;
-    }
-  } while (!WorkList.empty());
+      // Max the current height against this successor's height.
+      Cur->Height = std::max(Cur->Height, SuccSU->Height + I->getLatency());
+      ++I;
+    } while (I != E);
+
+    // We've examined all successors of this SU, our height is now current.
+    Cur->isHeightCurrent = true;
+
+    // If there are no further nodes to process, we're finished.
+    if (Stack.empty())
+      return;
+
+    // Otherwise pop the stack and continue.
+#ifndef NDEBUG
+    Visited.erase(Cur);
+#endif
+    std::tie(Cur, I) = Stack.pop_back_val();
+  }
 }
 
 void SUnit::biasCriticalPath() {