[ScheduleDAG] Don't schedule node with physical register interference

[efriedma]

Summary

https://reviews.llvm.org/D31536 didn't really solve the problem it was trying to solve; it got rid of the assertion failure, but we were still scheduling the DAG incorrectly (mixing together instructions from different calls), leading to a MachineVerifier failure.

In order to schedule the DAG correctly, we have to make sure we don't schedule a node which should be blocked by an interference. Fix ScheduleDAGRRList::PickNodeToScheduleBottomUp so it doesn't pick a node like that.

The added call to FindAvailableNode() is the key change here; this makes sure we don't try to schedule a call while we're in the middle of scheduling a different call. I'm not sure this is the right approach; in particular, I'm not sure how to prove we don't end up with an infinite loop of repeatedly backtracking.

This also reverts the code change from D31536. It doesn't do anything useful: we should never schedule an ADJCALLSTACKDOWN unless we've already scheduled the corresponding ADJCALLSTACKUP.

[efriedma]

Ping.

[javed.absar]

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

552

FindCallSeqStart - line 476 : assert(Best); already checks, so this assertion seems redundant

[efriedma]

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

552

That's true along that particular codepath, but FindCallSeqStart can return null along other codepaths; the assertion isn't obviously redundant.

[samparker]

Hi Eli,

Thanks for taking a look at this again, but I don't think I can be of much help with my very limited understanding of this code. I have no idea if you're going to get stuck backtracking, hopefully Andrew can shine some light.

cheers,
sam

[efriedma]

Ping.

[efriedma]

Ping^2

[atrick]

LGTM. Thanks.

lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
   unsigned CallResource = TRI->getNumRegs();
   if (!LiveRegDefs[CallResource])
     for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())
       if (Node->isMachineOpcode() &&
           Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
         unsigned NestLevel = 0;
         unsigned MaxNest = 0;
         SDNode *N = FindCallSeqStart(Node, NestLevel, MaxNest, TII);
+        assert(N && "Must find call sequence start");
 
         SUnit *Def = &SUnits[N->getNodeId()];
         CallSeqEndForStart[Def] = SU;
 
         ++NumLiveRegs;
         LiveRegDefs[CallResource] = Def;
         LiveRegGens[CallResource] = SU;
         break;
void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
 
   // Reclaim the special call resource dependence, if this is the beginning
   // of a call.
   unsigned CallResource = TRI->getNumRegs();
   for (const SDNode *SUNode = SU->getNode(); SUNode;
        SUNode = SUNode->getGluedNode()) {
     if (SUNode->isMachineOpcode() &&
         SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
+      SUnit *SeqEnd = CallSeqEndForStart[SU];
+      assert(SeqEnd && "Call sequence start/end must be known");
+      assert(!LiveRegDefs[CallResource]);
+      assert(!LiveRegGens[CallResource]);
       ++NumLiveRegs;
       LiveRegDefs[CallResource] = SU;
-      LiveRegGens[CallResource] = CallSeqEndForStart[SU];
+      LiveRegGens[CallResource] = SeqEnd;
     }
   }
 
   // Release the special call resource dependence, if this is the end
   // of a call.
   if (LiveRegGens[CallResource] == SU)
     for (const SDNode *SUNode = SU->getNode(); SUNode;
          SUNode = SUNode->getGluedNode()) {
       if (SUNode->isMachineOpcode() &&
           SUNode->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
+        assert(LiveRegDefs[CallResource]);
+        assert(LiveRegGens[CallResource]);
         --NumLiveRegs;
         LiveRegDefs[CallResource] = nullptr;
         LiveRegGens[CallResource] = nullptr;
         releaseInterferences(CallResource);
       }
     }
 
   for (auto &Succ : SU->Succs) {
if (Node->getOpcode() == ISD::INLINEASM) {
       continue;
     }
 
     if (!Node->isMachineOpcode())
       continue;
     // If we're in the middle of scheduling a call, don't begin scheduling
     // another call. Also, don't allow any physical registers to be live across
     // the call.
-    if ((Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) ||
-        (Node->getMachineOpcode() == TII->getCallFrameSetupOpcode())) {
+    if (Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
       // Check the special calling-sequence resource.
       unsigned CallResource = TRI->getNumRegs();
       if (LiveRegDefs[CallResource]) {
         SDNode *Gen = LiveRegGens[CallResource]->getNode();
         while (SDNode *Glued = Gen->getGluedNode())
           Gen = Glued;
         if (!IsChainDependent(Gen, Node, 0, TII) &&
             RegAdded.insert(CallResource).second)

 }
 
 /// Return a node that can be scheduled in this cycle. Requirements:
 /// (1) Ready: latency has been satisfied
 /// (2) No Hazards: resources are available
 /// (3) No Interferences: may unschedule to break register interferences.
 SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
   SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();
+  auto FindAvailableNode = [&]() {
     while (CurSU) {
       SmallVector<unsigned, 4> LRegs;
       if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
         break;
       DEBUG(dbgs() << "    Interfering reg " <<
             (LRegs[0] == TRI->getNumRegs() ? "CallResource"
              : TRI->getName(LRegs[0]))
              << " SU #" << CurSU->NodeNum << '\n');
       std::pair<LRegsMapT::iterator, bool> LRegsPair =
         LRegsMap.insert(std::make_pair(CurSU, LRegs));
       if (LRegsPair.second) {
         CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
         Interferences.push_back(CurSU);
       }
       else {
         assert(CurSU->isPending && "Interferences are pending");
         // Update the interference with current live regs.
         LRegsPair.first->second = LRegs;
       }
       CurSU = AvailableQueue->pop();
     }
+  };
+  FindAvailableNode();
   if (CurSU)
     return CurSU;
 
   // All candidates are delayed due to live physical reg dependencies.
   // Try backtracking, code duplication, or inserting cross class copies
   // to resolve it.
   for (SUnit *TrySU : Interferences) {
     SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
if (!WillCreateCycle(TrySU, BtSU))  {
           AvailableQueue->remove(BtSU);
       }
       DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum << ") to SU("
             << TrySU->NodeNum << ")\n");
       AddPred(TrySU, SDep(BtSU, SDep::Artificial));
 
       // If one or more successors has been unscheduled, then the current
       // node is no longer available.
-      if (!TrySU->isAvailable || !TrySU->NodeQueueId)
+      if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
+        DEBUG(dbgs() << "TrySU not available; choosing node from queue\n");
         CurSU = AvailableQueue->pop();
-      else {
+      } else {
+        DEBUG(dbgs() << "TrySU available\n");        
         // Available and in AvailableQueue
         AvailableQueue->remove(TrySU);
         CurSU = TrySU;
       }
+      FindAvailableNode();
       // Interferences has been mutated. We must break.
       break;
     }
   }
 
   if (!CurSU) {
     // Can't backtrack. If it's too expensive to copy the value, then try
     // duplicate the nodes that produces these "too expensive to copy"

test/CodeGen/ARM/unschedule-first-call.ll

-; RUN: llc < %s
+; RUN: llc -verify-machineinstrs < %s
 ; PR30911
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 target triple = "armv6kz--linux-gnueabihf"
 
 ; Function Attrs: nounwind
 define void @dradbg(i32, i32, float*, float*, float*, float*, float*) #0 {
   br i1 undef, label %.critedge, label %8