[CodeGen] Add support for instruction clusters

[evandro]

Summary

Perform the clustering of instructions in the scheduler by using information from the machine model.

[javed.absar]

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

242

May be I am bit confused here, but should it not be SDep(Def, SDep::Artificial) ?
Please consider rewording the comment to make the intention clearer, if possible.

[evandro]

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

242

For each instruction, go over its predecessors looking for any instruction that's clustered to it. Then, go over the successors of the clustered instruction and bind them to the original instruction.

[javed.absar]

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

242

Thanks, much clearer. May this reply could be added as comment.

[evandro]

Address feedback by @javed.absar.

[MatzeB]

I'm not sure I like this:

• It introduces a new word "cluster", so we end up having the words "MacroFusion" and "Cluster" around which appear to mean the same thing?
• Using computeOperandLatency() to compute something called cluster feels out of place, similar with getReadAdvanceCycles

llvm/include/llvm/CodeGen/TargetSchedule.h

#endif
   }
 
   /// \brief Compute operand latency based on the available machine model.
   ///
   /// Compute and return the latency of the given data dependent def and use
   /// when the operand indices are already known. UseMI may be NULL for an
   /// unknown user.
   unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx,
-                                 const MachineInstr *UseMI, unsigned UseOperIdx)
-    const;
+                                 const MachineInstr *UseMI, unsigned UseOperIdx,
+                                 bool *Cluster = nullptr) const;
 
   /// \brief Compute the instruction latency based on the available machine
   /// model.
   ///
   /// Compute and return the expected latency of this instruction independent of
   /// a particular use. computeOperandLatency is the preferred API, but this is
   /// occasionally useful to help estimate instruction cost.
   ///

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

auto allMMOsOkay = [&]() {
     }
     return true;
   };
 
   if (!allMMOsOkay())
     Objects.clear();
 }
 
+// Chain the dependents of the instruction defining a cluster to the instruction
+// clustered to it to prevent them from being scheduled between the clustered
+// instructions.
+static void addClusterChain(SUnit *SU) {
+  for (auto &Def : SU->Preds)
+    if (Def.isCluster())
+      for (auto &Use : Def.getSUnit()->Succs) {
+        SUnit *UseSU = Use.getSUnit();
+        if (UseSU == SU || UseSU->isPred(SU))
+          continue;
+        DEBUG(dbgs() << "  Bind ";
+              SU->print(dbgs()); dbgs() << " - ";
+              UseSU->print(dbgs()); dbgs() << '\n';);
+        UseSU->addPred(SDep(SU, SDep::Artificial));
+      }
+}
+
 void ScheduleDAGInstrs::startBlock(MachineBasicBlock *bb) {
   BB = bb;
 }
 
 void ScheduleDAGInstrs::finishBlock() {
   // Subclasses should no longer refer to the old block.
   BB = nullptr;
 }
for (MCRegAliasIterator Alias(MO.getReg(), TRI, true);
     for (Reg2SUnitsMap::iterator I = Uses.find(*Alias); I != Uses.end(); ++I) {
       SUnit *UseSU = I->SU;
       if (UseSU == SU)
         continue;
 
       // Adjust the dependence latency using operand def/use information,
       // then allow the target to perform its own adjustments.
       int UseOp = I->OpIdx;
-      MachineInstr *RegUse = nullptr;
+      MachineInstr *UseMI = nullptr;
       SDep Dep;
+      bool Cluster;
       if (UseOp < 0)
         Dep = SDep(SU, SDep::Artificial);
       else {
         // Set the hasPhysRegDefs only for physreg defs that have a use within
         // the scheduling region.
         SU->hasPhysRegDefs = true;
         Dep = SDep(SU, SDep::Data, *Alias);
-        RegUse = UseSU->getInstr();
+        UseMI = UseSU->getInstr();
       }
-      Dep.setLatency(
-        SchedModel.computeOperandLatency(SU->getInstr(), OperIdx, RegUse,
-                                         UseOp));
-
+      Dep.setLatency(SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
+                                                      UseMI, UseOp, &Cluster));
       ST.adjustSchedDependency(SU, UseSU, Dep);
       UseSU->addPred(Dep);
+      if (Cluster) {
+        DEBUG(dbgs() << "  Cluster ";
+              SU->print(dbgs(), this); dbgs() << " - ";
+              UseSU->print(dbgs(), this); dbgs() << '\n';);
+        UseSU->addPred(SDep(SU, SDep::Cluster));
+      }
     }
   }
 }
 
 /// \brief Adds 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) {
for (VReg2SUnitOperIdxMultiMap::iterator I = CurrentVRegUses.find(Reg),
       // Ignore uses of other lanes.
       if ((LaneMask & KillLaneMask).none()) {
         ++I;
         continue;
       }
 
       if ((LaneMask & DefLaneMask).any()) {
         SUnit *UseSU = I->SU;
-        MachineInstr *Use = UseSU->getInstr();
+        MachineInstr *UseMI = UseSU->getInstr();
         SDep Dep(SU, SDep::Data, Reg);
-        Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx, Use,
-                                                        I->OperandIndex));
+        bool Cluster;
+        Dep.setLatency(SchedModel.computeOperandLatency(MI, OperIdx,
+                                                        UseMI, I->OperandIndex,
+                                                        &Cluster));
         ST.adjustSchedDependency(SU, UseSU, Dep);
         UseSU->addPred(Dep);
+        if (Cluster) {
+          DEBUG(dbgs() << "  Cluster ";
+                SU->print(dbgs(), this); dbgs() << " - ";
+                UseSU->print(dbgs(), this); dbgs() << '\n';);
+          UseSU->addPred(SDep(SU, SDep::Cluster));
+        }
       }
 
       LaneMask &= ~KillLaneMask;
       // If we found a Def for all lanes of this use, remove it from the list.
       if (LaneMask.any()) {
         I->LaneMask = LaneMask;
         ++I;
       } else
if (Stores.size() + Loads.size() >= HugeRegion) {
       reduceHugeMemNodeMaps(Stores, Loads, getReductionSize());
     }
     if (NonAliasStores.size() + NonAliasLoads.size() >= HugeRegion) {
       DEBUG(dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n";);
       reduceHugeMemNodeMaps(NonAliasStores, NonAliasLoads, getReductionSize());
     }
   }
 
+  // Bind any clusters.
+  addClusterChain(&ExitSU);
+  for (auto &I : MISUnitMap)
+    addClusterChain(I.second);
+
   if (DbgMI)
     FirstDbgValue = DbgMI;
 
   Defs.clear();
   Uses.clear();
   CurrentVRegDefs.clear();
   CurrentVRegUses.clear();
 }

llvm/lib/CodeGen/TargetSchedule.cpp

if (MO.isReg() && MO.readsReg() && !MO.isDef())
       ++UseIdx;
   }
   return UseIdx;
 }
 
 // Top-level API for clients that know the operand indices.
 unsigned TargetSchedModel::computeOperandLatency(
   const MachineInstr *DefMI, unsigned DefOperIdx,
-  const MachineInstr *UseMI, unsigned UseOperIdx) const {
+  const MachineInstr *UseMI, unsigned UseOperIdx, bool *Cluster) const {
+
+  if (Cluster != nullptr)
+    *Cluster = false;
 
   if (!hasInstrSchedModel() && !hasInstrItineraries())
     return TII->defaultDefLatency(SchedModel, *DefMI);
 
   if (hasInstrItineraries()) {
     int OperLatency = 0;
     if (UseMI) {
       OperLatency = TII->getOperandLatency(&InstrItins, *DefMI, DefOperIdx,
if (DefIdx < SCDesc->NumWriteLatencyEntries) {
     if (!UseMI)
       return Latency;
 
     // Lookup the use's latency adjustment in SubtargetInfo.
     const MCSchedClassDesc *UseDesc = resolveSchedClass(UseMI);
     if (UseDesc->NumReadAdvanceEntries == 0)
       return Latency;
     unsigned UseIdx = findUseIdx(UseMI, UseOperIdx);
-    int Advance = STI->getReadAdvanceCycles(UseDesc, UseIdx, WriteID);
+    int Advance = STI->getReadAdvanceCycles(UseDesc, UseIdx, WriteID, Cluster);
     if (Advance > 0 && (unsigned)Advance > Latency) // unsigned wrap
       return 0;
     return Latency - Advance;
   }
   // If DefIdx does not exist in the model (e.g. implicit defs), then return
   // unit latency (defaultDefLatency may be too conservative).
 #ifndef NDEBUG
   if (SCDesc->isValid() && !DefMI->getOperand(DefOperIdx).isImplicit()