- if (SU->Height == 0 || Height > SU->Height) {
- SU->Height = Height;
- for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
- I != E; ++I)
- WorkList.push_back(std::make_pair(I->Dep, Height+1));
+ unsigned &SUHeight = SU->Height;
+
+ // Use dynamic programming:
+ // When current node is being processed, all of its dependencies
+ // are already processed.
+ // So, just iterate over all successors and take the longest path
+ for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
+ I != E; ++I) {
+ unsigned SuccHeight = I->Dep->Height;
+ if (SuccHeight+1 > SUHeight) {
+ SUHeight = SuccHeight + 1;
+ }
+ }
+
+ // Update InDegrees of all nodes depending on current SUnit
+ for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
+ I != E; ++I) {
+ SUnit *SU = I->Dep;
+ if (!--InDegree[SU->NodeNum])
+ // If all dependencies of the node are processed already,
+ // then the longest path for the node can be computed now
+ WorkList.push_back(SU);