Add DAG mutation interface to the post-RA scheduler

[kparzysz]

Summary

This adds the ScheduleDAGMutation interface to the post-RA scheduler.

[atrick]

There's already a ScheduleDAGMutation interface for this purpose. The mutations are scheduled after ScheduDAGTopologicalSort so you can use that to avoid introducing cycles.

[kparzysz]

That would work, but it only applies to MachineScheduler. For us this would need to be available for any scheduler (including post-RA scheduler and the packetizer).

Could move the interface from ScheduleDAGMI to ScheduleDAGInstrs?

[atrick]

Each scheduler should be able to run with its own set of DAG post processing mutations.

Can you just add the interface to the Packetizer and PostRA scheduler?

Also consider using MachineScheduler for postRA scheduling. It's been supported for a very long time now.

Also, the per-operand machine model allows for the definition of predicates that compute latencies contextually.

[kparzysz]

The post-RA scheduler runs as a standalone optimization. Targets do not create their own subclass of the scheduler, so there needs to be some other way of supplying DAG mutations. There is a subtarget hook to provide critical path register classes, so I guess I could one to provide mutations as well, but it would then be specific to the post-RA scheduler. Would that be ok?

In the long term we would probably replace the post-RA scheduler with a packetizing scheduler that does more than the current DFA packetizer.

[atrick]

Yeah. I'm saying that the hook *should* be specific to the old postRA scheduler. Each scheduler should have it's own capability for mutating the DAG. They can all share the ScheduleDAGMutation interface to allow reuse.

[kparzysz]

Changed the approach as discussed earlier.

[atrick]

LGTM

llvm/trunk/include/llvm/CodeGen/MachineScheduler.h

 
 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
 #define LLVM_CODEGEN_MACHINESCHEDULER_H
 
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachinePassRegistry.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
+#include "llvm/CodeGen/ScheduleDAGMutation.h"
 #include <memory>
 
 namespace llvm {
 
 extern cl::opt<bool> ForceTopDown;
 extern cl::opt<bool> ForceBottomUp;
 
 class LiveIntervals;
public:
   /// When all predecessor dependencies have been resolved, free this node for
   /// top-down scheduling.
   virtual void releaseTopNode(SUnit *SU) = 0;
   /// When all successor dependencies have been resolved, free this node for
   /// bottom-up scheduling.
   virtual void releaseBottomNode(SUnit *SU) = 0;
 };
 
-/// Mutate the DAG as a postpass after normal DAG building.
-class ScheduleDAGMutation {
-  virtual void anchor();
-public:
-  virtual ~ScheduleDAGMutation() {}
-
-  virtual void apply(ScheduleDAGMI *DAG) = 0;
-};
-
 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
 /// schedules machine instructions according to the given MachineSchedStrategy
 /// without much extra book-keeping. This is the common functionality between
 /// PreRA and PostRA MachineScheduler.
 class ScheduleDAGMI : public ScheduleDAGInstrs {
 protected:
   AliasAnalysis *AA;
   LiveIntervals *LIS;

llvm/trunk/include/llvm/CodeGen/ScheduleDAGMutation.h

+//==- ScheduleDAGMutation.h - MachineInstr Scheduling ------------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the ScheduleDAGMutation class, which represents
+// a target-specific mutation of the dependency graph for scheduling.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_SCHEDULEDAGMUTATION_H
+#define LLVM_CODEGEN_SCHEDULEDAGMUTATION_H
+
+namespace llvm {
+  class ScheduleDAGInstrs;
+
+  /// Mutate the DAG as a postpass after normal DAG building.
+  class ScheduleDAGMutation {
+    virtual void anchor();
+  public:
+    virtual ~ScheduleDAGMutation() {}
+
+    virtual void apply(ScheduleDAGInstrs *DAG) = 0;
+  };
+}
+
+#endif

llvm/trunk/include/llvm/Target/TargetSubtargetInfo.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TARGET_TARGETSUBTARGETINFO_H
 #define LLVM_TARGET_TARGETSUBTARGETINFO_H
 
 #include "llvm/CodeGen/PBQPRAConstraint.h"
 #include "llvm/CodeGen/SchedulerRegistry.h"
+#include "llvm/CodeGen/ScheduleDAGMutation.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/Support/CodeGen.h"
+#include <vector>
 
 namespace llvm {
 
 class CallLowering;
 class DataLayout;
 class MachineFunction;
 class MachineInstr;
 class SDep;
public:
 
   // For use with PostRAScheduling: in CriticalPathRCs, return any register
   // classes that should only be considered for anti-dependence breaking if they
   // are on the critical path.
   virtual void getCriticalPathRCs(RegClassVector &CriticalPathRCs) const {
     return CriticalPathRCs.clear();
   }
 
+  // \brief Provide an ordered list of schedule DAG mutations for the post-RA
+  // scheduler.
+  virtual void getPostRAMutations(
+      std::vector<std::unique_ptr<ScheduleDAGMutation>> &Mutations) const {
+  }
+
   // For use with PostRAScheduling: get the minimum optimization level needed
   // to enable post-RA scheduling.
   virtual CodeGenOpt::Level getOptLevelToEnablePostRAScheduler() const {
     return CodeGenOpt::Default;
   }
 
   /// \brief True if the subtarget should run the local reassignment
   /// heuristic of the register allocator.

llvm/trunk/lib/CodeGen/MachineScheduler.cpp

class LoadClusterMutation : public ScheduleDAGMutation {
 
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
 public:
   LoadClusterMutation(const TargetInstrInfo *tii,
                       const TargetRegisterInfo *tri)
     : TII(tii), TRI(tri) {}
 
-  void apply(ScheduleDAGMI *DAG) override;
+  void apply(ScheduleDAGInstrs *DAGInstrs) override;
 protected:
   void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG);
 };
 } // anonymous
 
 void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads,
                                                   ScheduleDAGMI *DAG) {
   SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords;
if (TII->shouldClusterLoads(SUa->getInstr(), SUb->getInstr(), ClusterLength)
       ++ClusterLength;
     }
     else
       ClusterLength = 1;
   }
 }
 
 /// \brief Callback from DAG postProcessing to create cluster edges for loads.
-void LoadClusterMutation::apply(ScheduleDAGMI *DAG) {
+void LoadClusterMutation::apply(ScheduleDAGInstrs *DAGInstrs) {
+  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
+
   // Map DAG NodeNum to store chain ID.
   DenseMap<unsigned, unsigned> StoreChainIDs;
   // Map each store chain to a set of dependent loads.
   SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents;
   for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
     SUnit *SU = &DAG->SUnits[Idx];
     if (!SU->getInstr()->mayLoad())
       continue;

 /// that may be fused by the processor into a single operation.
 class MacroFusion : public ScheduleDAGMutation {
   const TargetInstrInfo &TII;
   const TargetRegisterInfo &TRI;
 public:
   MacroFusion(const TargetInstrInfo &TII, const TargetRegisterInfo &TRI)
     : TII(TII), TRI(TRI) {}
 
-  void apply(ScheduleDAGMI *DAG) override;
+  void apply(ScheduleDAGInstrs *DAGInstrs) 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) {
+void MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
+  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
+
   // For now, assume targets can only fuse with the branch.
   SUnit &ExitSU = DAG->ExitSU;
   MachineInstr *Branch = ExitSU.getInstr();
   if (!Branch)
     return;
 
   for (SUnit &SU : DAG->SUnits) {
     // SUnits with successors can't be schedule in front of the ExitSU.
class CopyConstrain : public ScheduleDAGMutation {
   // Transient state.
   SlotIndex RegionBeginIdx;
   // RegionEndIdx is the slot index of the last non-debug instruction in the
   // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
   SlotIndex RegionEndIdx;
 public:
   CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
 
-  void apply(ScheduleDAGMI *DAG) override;
+  void apply(ScheduleDAGInstrs *DAGInstrs) override;
 
 protected:
   void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);
 };
 } // anonymous
 
 /// constrainLocalCopy handles two possibilities:
 /// 1) Local src:
for (SmallVectorImpl<SUnit*>::const_iterator
     DEBUG(dbgs() << "  Global use SU(" << (*I)->NodeNum << ") -> SU("
           << FirstLocalSU->NodeNum << ")\n");
     DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak));
   }
 }
 
 /// \brief Callback from DAG postProcessing to create weak edges to encourage
 /// copy elimination.
-void CopyConstrain::apply(ScheduleDAGMI *DAG) {
+void CopyConstrain::apply(ScheduleDAGInstrs *DAGInstrs) {
+  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
   assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
 
   MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end());
   if (FirstPos == DAG->end())
     return;
   RegionBeginIdx = DAG->getLIS()->getInstructionIndex(*FirstPos);
   RegionEndIdx = DAG->getLIS()->getInstructionIndex(
       *priorNonDebug(DAG->end(), DAG->begin()));

llvm/trunk/lib/CodeGen/PostRASchedulerList.cpp

class SchedulePostRATDList : public ScheduleDAGInstrs {
     AntiDepBreaker *AntiDepBreak;
 
     /// AA - AliasAnalysis for making memory reference queries.
     AliasAnalysis *AA;
 
     /// The schedule. Null SUnit*'s represent noop instructions.
     std::vector<SUnit*> Sequence;
 
+    /// Ordered list of DAG postprocessing steps.
+    std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
+
     /// The index in BB of RegionEnd.
     ///
     /// This is the instruction number from the top of the current block, not
     /// the SlotIndex. It is only used by the AntiDepBreaker.
     unsigned EndIndex;
 
   public:
     SchedulePostRATDList(
public:
     ///
     void Observe(MachineInstr &MI, unsigned Count);
 
     /// finishBlock - Clean up register live-range state.
     ///
     void finishBlock() override;
 
   private:
+    /// Apply each ScheduleDAGMutation step in order.
+    void postprocessDAG();
+
     void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
     void ReleaseSuccessors(SUnit *SU);
     void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
     void ListScheduleTopDown();
 
     void dumpSchedule() const;
     void emitNoop(unsigned CurCycle);
   };
SchedulePostRATDList::SchedulePostRATDList(
     SmallVectorImpl<const TargetRegisterClass *> &CriticalPathRCs)
     : ScheduleDAGInstrs(MF, &MLI), AA(AA), EndIndex(0) {
 
   const InstrItineraryData *InstrItins =
       MF.getSubtarget().getInstrItineraryData();
   HazardRec =
       MF.getSubtarget().getInstrInfo()->CreateTargetPostRAHazardRecognizer(
           InstrItins, this);
+  MF.getSubtarget().getPostRAMutations(Mutations);
 
   assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE ||
           MRI.tracksLiveness()) &&
          "Live-ins must be accurate for anti-dependency breaking");
   AntiDepBreak =
     ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ?
      (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) :
      ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ?

 void SchedulePostRATDList::finishBlock() {
   if (AntiDepBreak)
     AntiDepBreak->FinishBlock();
 
   // Call the superclass.
   ScheduleDAGInstrs::finishBlock();
 }
 
+/// Apply each ScheduleDAGMutation step in order.
+void SchedulePostRATDList::postprocessDAG() {
+  for (auto &M : Mutations)
+    M->apply(this);
+}
+
 //===----------------------------------------------------------------------===//
 //  Top-Down Scheduling
 //===----------------------------------------------------------------------===//
 
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 /// the PendingQueue if the count reaches zero.
 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
   SUnit *SuccSU = SuccEdge->getSUnit();