Index: llvm/include/llvm/CodeGen/MachinePipeliner.h
===================================================================
--- llvm/include/llvm/CodeGen/MachinePipeliner.h
+++ llvm/include/llvm/CodeGen/MachinePipeliner.h
@@ -332,22 +332,38 @@
 
   NodeSet() = default;
   NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
+    // The following Latency calculation Assumes that the NodeNum for the
+    // SUnits in path S -> ... -> E is monotonically increasing. This is
+    // guaranteed, for example, by Johnson's Circuit algorithm with an ordering
+    // defined by SUnit::NodeNum.
+    //
+    // Future calls to insert/remove nodes from this NodeSet may break the
+    // below calculation.
+    //
+    // See SwingSchedulerDAG::findCircuits.
+    //
+    // [1] Donald B. Johnson, Finding all the elementary circuits of a directed
+    //     graph, SIAM Journal on Computing, 1975.
     Latency = 0;
     for (unsigned i = 0, e = Nodes.size(); i < e; ++i) {
-      DenseMap<SUnit *, unsigned> SuccSUnitLatency;
+      // The next node is either the next node in the list, or the backedge to
+      // the first node
+      SUnit *NextSUnit = Nodes[(i + 1) % e];
+
+      // Calculate the maximum latency to NextSUnit from Nodes[i]
+      const SDep *MaxEdge = nullptr;
       for (const SDep &Succ : Nodes[i]->Succs) {
-        auto SuccSUnit = Succ.getSUnit();
-        if (!Nodes.count(SuccSUnit))
+        SUnit *SuccSUnit = Succ.getSUnit();
+        // Skip edges that are not part of this circuit
+        if (SuccSUnit->NodeNum != NextSUnit->NodeNum)
           continue;
+
         unsigned CurLatency = Succ.getLatency();
-        unsigned MaxLatency = 0;
-        if (SuccSUnitLatency.count(SuccSUnit))
-          MaxLatency = SuccSUnitLatency[SuccSUnit];
-        if (CurLatency > MaxLatency)
-          SuccSUnitLatency[SuccSUnit] = CurLatency;
+        if ((MaxEdge == nullptr) || (CurLatency > MaxEdge->getLatency()))
+          MaxEdge = &Succ;
       }
-      for (auto SUnitLatency : SuccSUnitLatency)
-        Latency += SUnitLatency.second;
+      assert(MaxEdge != nullptr && "Expected path successor in circuit");
+      Latency += MaxEdge->getLatency();
     }
   }