Index: llvm/include/llvm/CodeGen/MachinePipeliner.h =================================================================== --- llvm/include/llvm/CodeGen/MachinePipeliner.h +++ llvm/include/llvm/CodeGen/MachinePipeliner.h @@ -332,22 +332,35 @@ 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 SuccSUnitLatency; + // The next node is either the next node in the list, or the backedge to + // the first node + SUnit *NextSUnit = ((i + 1) == e) ? Nodes[0] : Nodes[i + 1]; + + // Calculate the maximum latency to NextSUnit from Nodes[i] + unsigned SuccLatency = 0; for (const SDep &Succ : Nodes[i]->Succs) { - auto SuccSUnit = Succ.getSUnit(); - if (!Nodes.count(SuccSUnit)) + SUnit *SuccSUnit = Succ.getSUnit(); + 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 (CurLatency > SuccLatency) + SuccLatency = CurLatency; } - for (auto SUnitLatency : SuccSUnitLatency) - Latency += SUnitLatency.second; + Latency += SuccLatency; } }