MachineScheduler: Restrict macroop fusion to data-dependent instructions.

[MatzeB]

Summary

Before creating a schedule edge to encourage MacroOpFusion check that:

• The predecessor actually writes a register that the branch reads.
• The predecessor has no successors in the ScheduleDAG so we can schedule it in front of the branch.

This avoids skewing the scheduling heuristic in cases where macroop
fusion cannot happen anyway.

[MatzeB]

ping

[MatzeB]

ping2

[john.brawn]

Looks generally OK to me, with one comment. Arguably the HasDataDep check should be done inside of shouldScheduleAdjacent as it is potentially possibly that there's some target that does instruction fusion on instructions without a data dependency, but neither of the two targets that currently define shouldScheduleAdjacent do, and it would be a rather strange thing to do as well, so I think it's OK.

lib/CodeGen/MachineScheduler.cpp

1362–1382

According to MCInstrDesc.h def operands are always registers, so inverting this to loop over the defs of Other would simplify things. You can also replace the inner loop with MachineInstr::readsRegister, which looks like it does the subregister checking that you want when passed a TargetRegisterInfo.

[MatzeB]

In D10745#204649, @john.brawn wrote:

Looks generally OK to me, with one comment. Arguably the HasDataDep check should be done inside of shouldScheduleAdjacent as it is potentially possibly that there's some target that does instruction fusion on instructions without a data dependency, but neither of the two targets that currently define shouldScheduleAdjacent do, and it would be a rather strange thing to do as well, so I think it's OK.

I haven't heard of any architecture that fuses unrelated operations. If such a thing comes up then we can still add an option to the Mutator or the respective target can simply create a mutator of its own.

lib/CodeGen/MachineScheduler.cpp

1362–1382

Unfortunately MachineInstr::defs() only includes the explicit register defs, there may be additional implicit defs later in the operand list.

[john.brawn]

lib/CodeGen/MachineScheduler.cpp

1362–1382

Ah, I see. I think you could still use MachineInstr::definesRegister instead of the inner loop though?

[MatzeB]

Good point John, this new version uses MachineInstr::modifiesRegister() instead of a manual loop.

[john.brawn]

LGTM

lib/CodeGen/MachineScheduler.cpp

 //===----------------------------------------------------------------------===//
 // MacroFusion - DAG post-processing to encourage fusion of macro ops.
 //===----------------------------------------------------------------------===//
 
 namespace {
 /// \brief Post-process the DAG to create cluster edges between instructions
 /// that may be fused by the processor into a single operation.
 class MacroFusion : public ScheduleDAGMutation {
-  const TargetInstrInfo *TII;
+  const TargetInstrInfo &TII;
+  const TargetRegisterInfo &TRI;
 public:
-  MacroFusion(const TargetInstrInfo *tii): TII(tii) {}
+  MacroFusion(const TargetInstrInfo &TII, const TargetRegisterInfo &TRI)
+    : TII(TII), TRI(TRI) {}
 
   void apply(ScheduleDAGMI *DAG) override;
 };
 } // anonymous
 
+/// Returns true if \p MI reads a register written by \p Other.
+static bool HasDataDep(const TargetRegisterInfo &TRI, const MachineInstr &MI,
+                       const MachineInstr &Other) {
+  for (const MachineOperand &MO : MI.uses()) {
+    if (!MO.isReg() || !MO.readsReg())
+      continue;
+
+    unsigned Reg = MO.getReg();
+    if (Other.modifiesRegister(Reg, &TRI))
+      return true;
+  }
+  return false;
+}
+
 /// \brief Callback from DAG postProcessing to create cluster edges to encourage
 /// fused operations.
 void MacroFusion::apply(ScheduleDAGMI *DAG) {
   // For now, assume targets can only fuse with the branch.
-  MachineInstr *Branch = DAG->ExitSU.getInstr();
+  SUnit &ExitSU = DAG->ExitSU;
+  MachineInstr *Branch = ExitSU.getInstr();
   if (!Branch)
     return;
 
-  for (unsigned Idx = DAG->SUnits.size(); Idx > 0;) {
-    SUnit *SU = &DAG->SUnits[--Idx];
-    if (!TII->shouldScheduleAdjacent(SU->getInstr(), Branch))
+  for (SUnit &SU : DAG->SUnits) {
+    // SUnits with successors can't be schedule in front of the ExitSU.
+    if (!SU.Succs.empty())
+      continue;
+    // We only care if the node writes to a register that the branch reads.
+    MachineInstr *Pred = SU.getInstr();
+    if (!HasDataDep(TRI, *Branch, *Pred))
+      continue;
+
+    if (!TII.shouldScheduleAdjacent(Pred, Branch))
       continue;
 
     // Create a single weak edge from SU to ExitSU. The only effect is to cause
     // bottom-up scheduling to heavily prioritize the clustered SU.  There is no
     // need to copy predecessor edges from ExitSU to SU, since top-down
     // scheduling cannot prioritize ExitSU anyway. To defer top-down scheduling
     // of SU, we could create an artificial edge from the deepest root, but it
     // hasn't been needed yet.
-    bool Success = DAG->addEdge(&DAG->ExitSU, SDep(SU, SDep::Cluster));
+    bool Success = DAG->addEdge(&ExitSU, SDep(&SU, SDep::Cluster));
     (void)Success;
     assert(Success && "No DAG nodes should be reachable from ExitSU");
 
-    DEBUG(dbgs() << "Macro Fuse SU(" << SU->NodeNum << ")\n");
+    DEBUG(dbgs() << "Macro Fuse SU(" << SU.NodeNum << ")\n");
     break;
   }
 }
 
 //===----------------------------------------------------------------------===//
 // CopyConstrain - DAG post-processing to encourage copy elimination.
 //===----------------------------------------------------------------------===//
 
static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C) {
   //
   // FIXME: extend the mutation API to allow earlier mutations to instantiate
   // data and pass it to later mutations. Have a single mutation that gathers
   // the interesting nodes in one pass.
   DAG->addMutation(make_unique<CopyConstrain>(DAG->TII, DAG->TRI));
   if (EnableLoadCluster && DAG->TII->enableClusterLoads())
     DAG->addMutation(make_unique<LoadClusterMutation>(DAG->TII, DAG->TRI));
   if (EnableMacroFusion)
-    DAG->addMutation(make_unique<MacroFusion>(DAG->TII));
+    DAG->addMutation(make_unique<MacroFusion>(*DAG->TII, *DAG->TRI));
   return DAG;
 }
 
 static MachineSchedRegistry
 GenericSchedRegistry("converge", "Standard converging scheduler.",
                      createGenericSchedLive);
 
 //===----------------------------------------------------------------------===//