[MachinePipeliner] Fix a bug in Output Dependency chains

[lsaba]

Summary

The current implementation collects all Preds/Succs of a Dep of kind Output, creating a long chain and subsequently a schedule with an unnecessarily large II.
Was this done on purpose for a reason I'm missing?

[bcahoon]

Thanks for the patch! Your suggested change is correct. The original code only "worked" because output dependences are rare. But, I can see that if the DAG is more complicated, and there is a mix of output and order dependences, that the original code would cause problems when computing the MII. If you have a test case, please add one.

Thanks,
Brendon

[lsaba]

I can't seem to get commit access to GitHub (already emailed llvm-admin twice)
Would anyone be kind enough to commit the change on behalf of me? Thanks!

[jsji]

I will commit it for you.

[lsaba]

In D75424#1939185, @jsji wrote:

I will commit it for you.

Thanks!

llvm/lib/CodeGen/MachinePipeliner.cpp

while (!Worklist.empty()) {
     SUnit *PrevSU = Cur.getSUnit();
     if (Visited.count(PrevSU))
       continue;
     std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(PrevSU);
     if (it == InstrToCycle.end())
       continue;
     EarlyCycle = std::min(EarlyCycle, it->second);
     for (const auto &PI : PrevSU->Preds)
-      if (PI.getKind() == SDep::Order || Dep.getKind() == SDep::Output)
+      if (PI.getKind() == SDep::Order || PI.getKind() == SDep::Output)
         Worklist.push_back(PI);
     Visited.insert(PrevSU);
   }
   return EarlyCycle;
 }
 
 // Return the cycle of the latest scheduled instruction in the chain.
 int SMSchedule::latestCycleInChain(const SDep &Dep) {
   SmallPtrSet<SUnit *, 8> Visited;
   SmallVector<SDep, 8> Worklist;
   Worklist.push_back(Dep);
   int LateCycle = INT_MIN;
   while (!Worklist.empty()) {
     const SDep &Cur = Worklist.pop_back_val();
     SUnit *SuccSU = Cur.getSUnit();
     if (Visited.count(SuccSU))
       continue;
     std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SuccSU);
     if (it == InstrToCycle.end())
       continue;
     LateCycle = std::max(LateCycle, it->second);
     for (const auto &SI : SuccSU->Succs)
-      if (SI.getKind() == SDep::Order || Dep.getKind() == SDep::Output)
+      if (SI.getKind() == SDep::Order || SI.getKind() == SDep::Output)
         Worklist.push_back(SI);
     Visited.insert(SuccSU);
   }
   return LateCycle;
 }
 
 /// If an instruction has a use that spans multiple iterations, then
 /// return true. These instructions are characterized by having a back-ege