[MachineScheduler] Handle regmasks and allow calls to be rescheduled.

[jonpa]

Summary

I have experimented with rescheduling calls in MachineScheduler, and have a
patch I would like to offer for comments and review. As far as I could
understand from the comment above isSchedBoundary(), this is something that
may be wanted generally.

Or is it otherwise a good enough option to use the pre-RA (isel) scheduler
to handle this?

This patch adds:

Handling of regmasks while building the dag, with a new ScheduleDAGInstrs
method 'addRegMaskDeps()'.

A new method 'clearCallsInDefsForReg()' has been added from code factored
out of addPhysRegDeps(), as it is also needed by addRegMaskDeps().

A new method SURegDefIsDead() that checks for a dead-def reg MO, and also
for a regmask, as opposed to calling registerDefIsDead(), which does not check
for the regmask.

A new SubtargetInfo virtual method 'MISchedRescheduleCalls()' and a new
CL option 'RescheduleCalls' to control the behaviour. Default is false, i.e.
no rescheduling of calls.

[hfinkel]

The obvious high-level question is: What do we gain by scheduling calls, and what's the right way to model them? Are you just trying to reduce register pressure in the caller, or are there other benefits as well?

(I suspect there are gains to be had by scheduling calls to reduce register pressure, regardless of anything else, but it is not immediately clear from your patch that this is what would happen).

[jonpa]

I noticed the comment phrasing including "currently" about the scheduler not handling calls, so I thought there might be some general interest.

For SystemZ this may be of interest also post-ra for the purpose of decoding, but that is just experimentation so far.

More scheduling freedom pre-ra would also be possible, and perhaps this would be good in some cases.

Otherwise, I am not really sure at the moment how needed this is.

[hfinkel]

In D15667#342810, @jonpa wrote:

I noticed the comment phrasing including "currently" about the scheduler not handling calls, so I thought there might be some general interest.

For SystemZ this may be of interest also post-ra for the purpose of decoding, but that is just experimentation so far.

More scheduling freedom pre-ra would also be possible, and perhaps this would be good in some cases.

Otherwise, I am not really sure at the moment how needed this is.

I believe there is general interest. I'm interested, however, in specifically what motivated you to look at this. Can you explain how decoding is relevant here?

[jonpa]

Considering that different instructions may have different grouping rules, meaning that in some cases some instructions can only go in certain slots and so on, a greater freedom for the scheduler should generally be good. I think I became interested in this while looking at some functions with long chains of calls. But, as I said, this is just experimentation so far.

[atrick]

High level, I have the same questions as Hal. But I'm not opposed to adding the support so that targets can evaluate the possibility of call scheduling.

Please test correctness at least on x86 by running the InstructionShuffler with RescheduleCalls.

lib/CodeGen/MachineScheduler.cpp

401–406

Don't we still want to call TII->isSchedulingBoundary for calls? The target may treat some calls differently. How about this:

Always honor the command line option if present (it's just for debugging/experimentation anyway):

if (RescheduleCalls.getNumOccurrences())
    return !RescheduleCalls;

Otherwise simply defer to the target:

return TII->isSchedulingBoundary(MI, MBB, *MF);

By default, have TargetInstrInfo::isSchedulingBoundary return true for isCall().

Make sure any in-tree targets that override this method return true for isCall().

Post on llvm-dev explaining that the scheduler now works across calls. If you have an out-of-tree target that overrides
TargetInstrInfo::isSchedulingBoundary, you now need to check isCall yourself.

lib/CodeGen/ScheduleDAGInstrs.cpp

324–329

I know this is copied code, but I don't understand why you break out of the loop here.

Also, I don't understand why you don't just clear all calls in your case, since you're about to add the most call to the Defs set.

344–345

I think this is a redundant check (as it is in addPhysRegDataDeps).

[atrick]

Please make sure we don't move reserved register definitions across calls. I'm not sure how those are reflected in the regmask.

[jonpa]

Changed the isSchedBoundary() function per request so that TII is used for calls handling.

Changes in clearCallsInDefsForReg() per suggestions to simply erase all previous calls before adding the current one.

New method addCallDeps(), to implement deps for reserved registers. I was not sure if all calls are guaranteed to have a regmask operand - in that case this method could have been eliminated and handled in addRegMaskDeps().

-misched=shuffle passes on X86.

Regarding the current discussion of compile time: this patch will make dags bigger, and potentially slower. Perhaps this should be checked?

With the test-suite on X86 (with default scheduler), I got:

Results

IMPROVED : 251
REGRESSED : 234

[atrick]

It would be nice to get this feature in. It's encouraging that misched=shuffle passes.

Matthias, could you review the register dependencies at call sites and comment on the regmask handling?

For this to be a real feature, we need test cases and a way for subtargets to opt-in.

[MatzeB]

lib/CodeGen/ScheduleDAGInstrs.cpp

324–329

+1

Also arguments to calls are not necessarily dead, they may reside in callee saved registers. Simply forgetting about all call-induced Defs seems invalid to me.

334–336

Have you actually tried without this code. If the call potentially reads/writes a reserved register then it must announce that with a use/def machine operand. If it does not this is a bug that should be fixed in the target IMO.

360–361

Don't repeat the function name in the doxygen comment.

366

Variable names should start with uppercase letter.

367

Avoid indentation with if (!MO.clobbersPhysReg(reg)) continue;

371

register masks already contain all register, it should not be necessary to iterate over the aliases.

378

Variable name should start with upper case letter. This call could be deferred until we know that DefSU != SU.

379

Isn't defOp equivalent to !SURegDefIsDead()?

380

Maybe introduce a variable unsigned AliasReg = *Alias; so we don't need to remind ourself with a comment that *Alias is a register...

386–387

see above, I would expect it to simply erase all previous Defs for this register reg.

609–610

\p SU and \p Reg is better doxygen style.

611

I'd tend to pass a const MachineInstr & instead of const SUnit* here (nullptr is invalid and MachineInstr instead of SUnit makes the function useful in more contexts).

612

No space before (.

613

upper case.

615

Please avoid auto in cases where the type is not obvious, we also tend to use the variable name MO for machine operands in most other loops.

618–623

Do we need to take register aliases into account here?

626

no braces.

1035–1036

You can add a continue; here

1053–1054

See my comment in addCallDeps(). I really think calls should not be special in any way regarding register dependencies...

include/llvm/CodeGen/ScheduleDAGInstrs.h

public:
 
     /// Return a label for the region of code covered by the DAG.
     std::string getDAGName() const override;
 
     /// \brief Fix register kill flags that scheduling has made invalid.
     void fixupKills(MachineBasicBlock *MBB);
   protected:
     void initSUnits();
+    void clearCallsInDefsForReg(unsigned Reg);
     void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
+    void addCallDeps(SUnit *SU);
+    void addRegMaskDeps(SUnit *SU, unsigned OperIdx);
     void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
     void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
     void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
 
+    /// Check if the MI of SU has a dead def of Reg, or if MI clobbers
+    /// it according to a regmask.
+    bool SURegDefIsDead(const SUnit *SU, unsigned Reg);
+
     /// \brief PostRA helper for rewriting kill flags.
     void startBlockForKills(MachineBasicBlock *BB);
 
     /// \brief Toggle a register operand kill flag.
     ///
     /// Other adjustments may be made to the instruction if necessary. Return
     /// true if the operand has been deleted, false if not.
     bool toggleKillFlag(MachineInstr *MI, MachineOperand &MO);

lib/CodeGen/MachineScheduler.cpp

 
 // Experimental heuristics
 static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden,
   cl::desc("Enable scheduling for macro fusion."), cl::init(true));
 
 static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden,
   cl::desc("Verify machine instrs before and after machine scheduling"));
 
+static cl::opt<bool> RescheduleCalls(
+    "resched-calls",
+    cl::desc("Don't treat calls as scheduling boundaries in the machine "
+             "instruction scheduling pass."), cl::init(true),
+    cl::Hidden);
+
 // DAG subtrees must have at least this many nodes.
 static const unsigned MinSubtreeSize = 8;
 
 // Pin the vtables to this file.
 void MachineSchedStrategy::anchor() {}
 void ScheduleDAGMutation::anchor() {}
 
 //===----------------------------------------------------------------------===//
bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) {
 
   if (VerifyScheduling)
     MF->verify(this, "After post machine scheduling.");
   return true;
 }
 
 /// Return true of the given instruction should not be included in a scheduling
 /// region.
-///
-/// MachineScheduler does not currently support scheduling across calls. To
-/// handle calls, the DAG builder needs to be modified to create register
-/// anti/output dependencies on the registers clobbered by the call's regmask
-/// operand. In PreRA scheduling, the stack pointer adjustment already prevents
-/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
-/// the boundary, but there would be no benefit to postRA scheduling across
-/// calls this late anyway.
 static bool isSchedBoundary(MachineBasicBlock::iterator MI,
                             MachineBasicBlock *MBB,
                             MachineFunction *MF,
                             const TargetInstrInfo *TII) {
-  return MI->isCall() || TII->isSchedulingBoundary(MI, MBB, *MF);
+  // Calls rescheduling may be controlled by CL option.
+  if (MI->isCall() && !MI->isTerminator() && RescheduleCalls.getNumOccurrences())
+    return !RescheduleCalls;
+
+  return TII->isSchedulingBoundary(MI, MBB, *MF);
 }
 
 /// Main driver for both MachineScheduler and PostMachineScheduler.
 void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,
                                            bool FixKillFlags) {
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
 
   // Visit all machine basic blocks.
   //

lib/CodeGen/ScheduleDAGInstrs.cpp

for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) {
                                          UseOp));
 
       ST.adjustSchedDependency(SU, UseSU, Dep);
       UseSU->addPred(Dep);
     }
   }
 }
 
+void ScheduleDAGInstrs::clearCallsInDefsForReg(unsigned Reg) {
+  // Calls will not be reordered because of chain dependencies (see
+  // below). Since call operands are dead, calls may continue to be added
+  // to the DefList making dependence checking quadratic in the size of
+  // the block. Instead, we leave only one call at the back of the
+  // DefList, which will be added after this.
+  Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg);
+  Reg2SUnitsMap::iterator B = P.first;
+  Reg2SUnitsMap::iterator I = P.second;
+  for (bool isBegin = I == B; !isBegin; /* empty */) {
+    isBegin = (--I) == B;
+    if (I->SU->isCall)
+      I = Defs.erase(I);
+  }
+}
+
+void ScheduleDAGInstrs::addCallDeps(SUnit *SU) {
+  assert(SU->isCall);
+
+  // Make sure we don't move reserved register definitions across
+  // calls. (This would be unnecessary if they were guaranteed to
+  // always be part of a regmask operand on each call. Are they?)
+  for (unsigned reg = 1; reg < TRI->getNumRegs(); reg++) {
+    if (MRI.isReserved(reg)) {
+      // Add output depencencies on all reserved registers.
+      for (MCRegAliasIterator Alias(reg, TRI, true); Alias.isValid(); ++Alias) {
+        for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) {
+          SUnit *DefSU = I->SU;
+          if (DefSU == &ExitSU)
+            continue;
+
+          bool defOp = DefSU->getInstr()->definesRegister(*Alias);
+          if (DefSU != SU && defOp) {
+            SDep Dep(SU, SDep::Output, /*Reg=*/*Alias);
+            DefSU->addPred(Dep);
+          }
+        }
+      }
+
+      clearCallsInDefsForReg(reg);
+      Defs.insert(PhysRegSUOper(SU, -1, reg));
+    }
+  }
+}
+
+/// addRegMaskDeps - Handle regmasks to be able to reschedule around
+/// calls.
+void ScheduleDAGInstrs::addRegMaskDeps(SUnit *SU, unsigned OperIdx) {
+  MachineInstr *MI = SU->getInstr();
+  MachineOperand &MO = MI->getOperand(OperIdx);
+
+  for (unsigned reg = 1; reg < TRI->getNumRegs(); reg++) {
+    if (MO.clobbersPhysReg(reg)) {
+      // Add output depencencies on all clobberd registers. Calls are
+      // expected to have register operands for in/out arguments, so
+      // they are not handled here.
+      for (MCRegAliasIterator Alias(reg, TRI, true); Alias.isValid(); ++Alias) {
+        for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) {
+          SUnit *DefSU = I->SU;
+          if (DefSU == &ExitSU)
+            continue;
+
+          // Don't add dependency to another dead def or another regmask.
+          bool defOp = DefSU->getInstr()->definesRegister(*Alias);
+          if (DefSU != SU && defOp && !SURegDefIsDead(DefSU, *Alias)) {
+            SDep Dep(SU, SDep::Output, /*Reg=*/*Alias);
+            DefSU->addPred(Dep);
+          }
+        }
+      }
+
+      if (SU->isCall)
+        clearCallsInDefsForReg(reg);
+      Defs.insert(PhysRegSUOper(SU, -1, reg));
+    }
+  }
+}
+
 /// addPhysRegDeps - Add register dependencies (data, anti, and output) from
 /// this SUnit to following instructions in the same scheduling region that
 /// depend the physical register referenced at OperIdx.
 void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
   MachineInstr *MI = SU->getInstr();
   MachineOperand &MO = MI->getOperand(OperIdx);
 
   // Optionally add output and anti dependencies. For anti
   // dependencies we use a latency of 0 because for a multi-issue
   // target we want to allow the defining instruction to issue
   // in the same cycle as the using instruction.
   // TODO: Using a latency of 1 here for output dependencies assumes
   //       there's no cost for reusing registers.
   SDep::Kind Kind = MO.isUse() ? SDep::Anti : SDep::Output;
   for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
        Alias.isValid(); ++Alias) {
     if (!Defs.contains(*Alias))
       continue;
     for (Reg2SUnitsMap::iterator I = Defs.find(*Alias); I != Defs.end(); ++I) {
       SUnit *DefSU = I->SU;
       if (DefSU == &ExitSU)
         continue;
       if (DefSU != SU &&
           (Kind != SDep::Output || !MO.isDead() ||
-           !DefSU->getInstr()->registerDefIsDead(*Alias))) {
+           !SURegDefIsDead(DefSU, *Alias))) {
         if (Kind == SDep::Anti)
           DefSU->addPred(SDep(SU, Kind, /*Reg=*/*Alias));
         else {
           SDep Dep(SU, Kind, /*Reg=*/*Alias);
           Dep.setLatency(
             SchedModel.computeOutputLatency(MI, OperIdx, DefSU->getInstr()));
           DefSU->addPred(Dep);
         }
void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) {
   else {
     addPhysRegDataDeps(SU, OperIdx);
     unsigned Reg = MO.getReg();
 
     // clear this register's use list
     if (Uses.contains(Reg))
       Uses.eraseAll(Reg);
 
-    if (!MO.isDead()) {
+    if (!MO.isDead())
       Defs.eraseAll(Reg);
-    } else if (SU->isCall) {
-      // Calls will not be reordered because of chain dependencies (see
-      // below). Since call operands are dead, calls may continue to be added
-      // to the DefList making dependence checking quadratic in the size of
-      // the block. Instead, we leave only one call at the back of the
-      // DefList.
-      Reg2SUnitsMap::RangePair P = Defs.equal_range(Reg);
-      Reg2SUnitsMap::iterator B = P.first;
-      Reg2SUnitsMap::iterator I = P.second;
-      for (bool isBegin = I == B; !isBegin; /* empty */) {
-        isBegin = (--I) == B;
-        if (!I->SU->isCall)
-          break;
-        I = Defs.erase(I);
-      }
-    }
+    else if (SU->isCall)
+      clearCallsInDefsForReg(Reg);
 
     // Defs are pushed in the order they are visited and never reordered.
     Defs.insert(PhysRegSUOper(SU, OperIdx, Reg));
   }
 }
 
 LaneBitmask ScheduleDAGInstrs::getLaneMaskForMO(const MachineOperand &MO) const
 {
if ((PrevDefLaneMask & LaneMask) == 0)
       continue;
     if (V2SU.SU == SU)
       continue;
 
     V2SU.SU->addPred(SDep(SU, SDep::Anti, Reg));
   }
 }
 
+/// Return true if SU has a dead register def operand of Reg, or a
+/// regmask that clobbers it, without having a live def of it as well.
+bool ScheduleDAGInstrs::SURegDefIsDead(const SUnit *SU, unsigned Reg) {
+  assert (TRI->isPhysicalRegister(Reg));
+  bool hasDeadDef = false;
+  MachineInstr *MI = SU->getInstr();
+  for (const auto &I : MI->operands()) {
+    if (I.isRegMask() && I.clobbersPhysReg(Reg))
+      hasDeadDef = true;
+    else if (I.isReg() && I.isDef() && I.getReg() == Reg) {
+      if (I.isDead())
+        hasDeadDef = true;
+      else
+        return false;
+    }
+  }
+
+  return (hasDeadDef);
+}
+
 /// Return true if MI is an instruction we are unable to reason about
 /// (like a call or something with unmodeled side effects).
 static inline bool isGlobalMemoryObject(AliasAnalysis *AA, MachineInstr *MI) {
   return MI->isCall() || MI->hasUnmodeledSideEffects() ||
          (MI->hasOrderedMemoryRef() && !MI->isInvariantLoad(AA));
 }
 
 /// This returns true if the two MIs need a chain edge between them.
for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
     assert(
         (CanHandleTerminators || (!MI->isTerminator() && !MI->isPosition())) &&
         "Cannot schedule terminators or labels!");
 
     // Add register-based dependencies (data, anti, and output).
     bool HasVRegDef = false;
     for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
       const MachineOperand &MO = MI->getOperand(j);
+      if (MO.isRegMask())
+        addRegMaskDeps(SU, j);
       if (!MO.isReg()) continue;
       unsigned Reg = MO.getReg();
       if (Reg == 0) continue;
 
       if (TRI->isPhysicalRegister(Reg))
         addPhysRegDeps(SU, j);
       else {
         if (MO.isDef()) {
           HasVRegDef = true;
           addVRegDefDeps(SU, j);
         }
         else if (MO.readsReg()) // ignore undef operands
           addVRegUseDeps(SU, j);
       }
     }
+
+    if (SU->isCall)
+      addCallDeps(SU);
+    
     // If we haven't seen any uses in this scheduling region, create a
     // dependence edge to ExitSU to model the live-out latency. This is required
     // for vreg defs with no in-region use, and prefetches with no vreg def.
     //
     // FIXME: NumDataSuccs would be more precise than NumSuccs here. This
     // check currently relies on being called before adding chain deps.
     if (SU->NumSuccs == 0 && SU->Latency > 1
         && (HasVRegDef || MI->mayLoad())) {