[X86] Make post-ra scheduling macrofusion-aware.

[courbet]

rebase

[courbet]

For the context: I'm experimenting with turning post-ra scheduling on for SNB onwards, and I some promising improvements. All the regressions I see are macro-fused instructions being moved apart, which this fixes.

[andreadb]

Nice patch Clement!

I always wondered why on x86 we only enabled that mutator in the pre-ra scheduler.
In the past, I remember I did some quick experiments with enabling that mutator in the post-RA scheduler. I must admit that I wasn't particularly lucky wih the experiments (i.e. I couldn't find significant/promising improvements). But then - again - those were just quick experiments, and I didn't try it on many codebases.

If you think you can share some numbers then that would be great.

On a slightly different topic: I often wondered whether we - at some point - we should start using the PostMIScheduler for X86.

Did you experiment with it?
The API is basically the same; mutators are run on the DAG as part of a dag-postprocessing step. You can try to enable that mutator on that pass too.
To enable PostMIScheduler however you have to substitutePass(&PostRASchedulerID, &PostMachineSchedulerID) in the X86PassConfig (similar to how AArch64 does it).
It would be interesting to see which one gives us the best codegen in your experiments.. (just curious).

[courbet]

In D59688#1439297, @andreadb wrote:

Nice patch Clement!

I always wondered why on x86 we only enabled that mutator in the pre-ra scheduler.
In the past, I remember I did some quick experiments with enabling that mutator in the post-RA scheduler. I must admit that I wasn't particularly lucky wih the experiments (i.e. I couldn't find significant/promising improvements). But then - again - those were just quick experiments, and I didn't try it on many codebases. If you think you can share some numbers then that would be great.

Thanks Andrea.

Yes, that's essentially what the comment in X86.td says:

"This generally gives a nice performance increase on silvermont, with largely neutral behavior on other contemporary large core processors."

However, that was before the round of scheduling information fixes that Simon & I made based on llvm-exegesis. I wanted to give it another try after that, and from my first experiments it seems that it indeed makes sense to look at it again.
What I have done for now is run our (internal, sorry) main macrobenchmark with post-ra enabled. With the base code I see a consistent regression of 0.5% to 1% depending on metrics. With this patch I see a consistent improvement of 0.5% to 2%.

On a slightly different topic: I often wondered whether we - at some point - we should start using the PostMIScheduler for X86.
Did you experiment with it?

I'm looking at all the options right now. But I want to make sure that we're comparing apples to apples, and that's why I'm fixing this.

When I'm done experimenting with different possibilities I'll write a summary of the results.

The API is basically the same; mutators are run on the DAG as part of a dag-postprocessing step. You can try to enable that mutator on that pass too.

Yup, I have another patch coming for this :)

[andreadb]

In D59688#1439350, @courbet wrote:

In D59688#1439297, @andreadb wrote:

Nice patch Clement!

I always wondered why on x86 we only enabled that mutator in the pre-ra scheduler.
In the past, I remember I did some quick experiments with enabling that mutator in the post-RA scheduler. I must admit that I wasn't particularly lucky wih the experiments (i.e. I couldn't find significant/promising improvements). But then - again - those were just quick experiments, and I didn't try it on many codebases. If you think you can share some numbers then that would be great.

Thanks Andrea.

Yes, that's essentially what the comment in X86.td says:

"This generally gives a nice performance increase on silvermont, with largely neutral behavior on other contemporary large core processors."

However, that was before the round of scheduling information fixes that Simon & I made based on llvm-exegesis. I wanted to give it another try after that, and from my first experiments it seems that it indeed makes sense to look at it again.
What I have done for now is run our (internal, sorry) main macrobenchmark with post-ra enabled. With the base code I see a consistent regression of 0.5% to 1% depending on metrics. With this patch I see a consistent improvement of 0.5% to 2%.

Thanks. That's good to know.
I plan to run some experiments today using your patch.

But in general, I am happy with this patch.

On a slightly different topic: I often wondered whether we - at some point - we should start using the PostMIScheduler for X86.
Did you experiment with it?

I'm looking at all the options right now. But I want to make sure that we're comparing apples to apples, and that's why I'm fixing this.

When I'm done experimenting with different possibilities I'll write a summary of the results.

The API is basically the same; mutators are run on the DAG as part of a dag-postprocessing step. You can try to enable that mutator on that pass too.

Yup, I have another patch coming for this :)

Cool. :-)

-Andrea

[courbet]

I plan to run some experiments today using your patch.

That's great, thanks.

[andreadb]

In D59688#1439408, @courbet wrote:

I plan to run some experiments today using your patch.

That's great, thanks.

Sorry, I was over optimistic about my other workload. I don't think I'll get a chance to get any perf numbers anytime soon.

That being said, I tried your patch on a few small examples on some different targets, and results seem good.
For example, before your patch I saw cases where the test/cmp was not emitted before the conditional branch. Your patch seems to fix that "issue" in most cases.

My only concern is that the macro-fusion mutator might be a bit too aggressive for AMD processors.
X86MacroFusion assumes that branch fusion can happen with ADD/SUB/INC/DEC too. That is okay for Intel processors, but not necessarily for AMD processors where branch fusion (as far as I remember) is limited to CMP/TEST opcodes only.
Since your patch enables that mutator for targets with FeatureMacroFusion, it would be nice to get some feedback from somebody with access to an AMD target where macro fusion is enabled (Bobcat/Jaguar doesn't do branch fusion). Perhaps @lebedev.ri can run some quick tests on BdVer2?
I don't think is a blocking issue, but in future we should revisit the logic in X86MacroFusion.

[lebedev.ri]

In D59688#1441464, @andreadb wrote:

In D59688#1439408, @courbet wrote:

I plan to run some experiments today using your patch.

That's great, thanks.

Sorry, I was over optimistic about my other workload. I don't think I'll get a chance to get any perf numbers anytime soon.

That being said, I tried your patch on a few small examples on some different targets, and results seem good.
For example, before your patch I saw cases where the test/cmp was not emitted before the conditional branch. Your patch seems to fix that "issue" in most cases.

My only concern is that the macro-fusion mutator might be a bit too aggressive for AMD processors.
X86MacroFusion assumes that branch fusion can happen with ADD/SUB/INC/DEC too. That is okay for Intel processors, but not necessarily for

In D59688#1441464, @andreadb wrote:

AMD processors where branch fusion (as far as I remember) is limited to CMP/TEST opcodes only.

That is consistent with what is stated in agner's microarchitecture, amd sog for piledriver.

Since your patch enables that mutator for targets with FeatureMacroFusion, it would be nice to get some feedback from somebody with access to an AMD target where macro fusion is enabled (Bobcat/Jaguar doesn't do branch fusion). Perhaps @lebedev.ri can run some quick tests on BdVer2?

It will, as usual, depend on whether this happens to affect the hotpath or not.
I did just run my rawspeed benchmark, and i'm not observing any notable non-noise perf changes.

I don't think is a blocking issue, but in future we should revisit the logic in X86MacroFusion.

While there, @andreadb, can you reply on https://reviews.llvm.org/D46662#1293043 ?

[andreadb]

In D59688#1442004, @lebedev.ri wrote:

In D59688#1441464, @andreadb wrote:

In D59688#1439408, @courbet wrote:

I plan to run some experiments today using your patch.

That's great, thanks.

Sorry, I was over optimistic about my other workload. I don't think I'll get a chance to get any perf numbers anytime soon.

That being said, I tried your patch on a few small examples on some different targets, and results seem good.
For example, before your patch I saw cases where the test/cmp was not emitted before the conditional branch. Your patch seems to fix that "issue" in most cases.

My only concern is that the macro-fusion mutator might be a bit too aggressive for AMD processors.
X86MacroFusion assumes that branch fusion can happen with ADD/SUB/INC/DEC too. That is okay for Intel processors, but not necessarily for

In D59688#1441464, @andreadb wrote:

AMD processors where branch fusion (as far as I remember) is limited to CMP/TEST opcodes only.

That is consistent with what is stated in agner's microarchitecture, amd sog for piledriver.

Since your patch enables that mutator for targets with FeatureMacroFusion, it would be nice to get some feedback from somebody with access to an AMD target where macro fusion is enabled (Bobcat/Jaguar doesn't do branch fusion). Perhaps @lebedev.ri can run some quick tests on BdVer2?

It will, as usual, depend on whether this happens to affect the hotpath or not.
I did just run my rawspeed benchmark, and i'm not observing any notable non-noise perf changes.

Thanks. That matches what I also saw in the past when I tested it.

I don't think is a blocking issue, but in future we should revisit the logic in X86MacroFusion.

While there, @andreadb, can you reply on https://reviews.llvm.org/D46662#1293043 ?

I replied to that code review (the two small benchmarks were available from one of Xur’s older posts).

[courbet]

I don't think is a blocking issue, but in future we should revisit the logic in X86MacroFusion.

For the record, this was dealt with in D59872.

[andreadb]

Thanks Clement.

LGTM

[lebedev.ri]

This could use test coverage i guess?

[courbet]

This could use test coverage i guess?

This is actually an NFC as the post-ra scheduler is not on by default. The next patch that enables scheduling will show the actual changes.

[lebedev.ri]

In D59688#1446142, @courbet wrote:

This could use test coverage i guess?

This is actually an NFC as the post-ra scheduler is not on by default. The next patch that enables scheduling will show the actual changes.

What about CPU's that specify let PostRAScheduler = 1; ?

[courbet]

What about CPU's that specify let PostRAScheduler = 1; ?

Ah yes, sorry I lost track of this. Interestingly there are no tests that fail currently. I'll try to come up with some that do.

For now I'll submit the refactoring part of this change (D59689).

[lebedev.ri]

In D59688#1446261, @courbet wrote:

What about CPU's that specify let PostRAScheduler = 1; ?

Ah yes, sorry I lost track of this. Interestingly there are no tests that fail currently.

I'll try to come up with some that do.

For now I'll submit the refactoring part of this change (D59689).

Thanks!

[courbet]

Add tests.

[lebedev.ri]

Please upload correct diff, this seems to be relative to previous patch.

[lebedev.ri]

nevermind, i see that it was committed in D59689.
Looks good.

llvm/include/llvm/CodeGen/MachineScheduler.h

 /// without much extra book-keeping. This is the common functionality between
 /// PreRA and PostRA MachineScheduler.
 class ScheduleDAGMI : public ScheduleDAGInstrs {
 protected:
   AliasAnalysis *AA;
   LiveIntervals *LIS;
   std::unique_ptr<MachineSchedStrategy> SchedImpl;
 
-  /// Topo - A topological ordering for SUnits which permits fast IsReachable
-  /// and similar queries.
-  ScheduleDAGTopologicalSort Topo;
-
   /// Ordered list of DAG postprocessing steps.
   std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
 
   /// The top of the unscheduled zone.
   MachineBasicBlock::iterator CurrentTop;
 
   /// The bottom of the unscheduled zone.
   MachineBasicBlock::iterator CurrentBottom;
 
   /// Record the next node in a scheduled cluster.
   const SUnit *NextClusterPred = nullptr;
   const SUnit *NextClusterSucc = nullptr;
 
 #ifndef NDEBUG
   /// The number of instructions scheduled so far. Used to cut off the
   /// scheduler at the point determined by misched-cutoff.
   unsigned NumInstrsScheduled = 0;
 #endif
 
 public:
   ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
                 bool RemoveKillFlags)
       : ScheduleDAGInstrs(*C->MF, C->MLI, RemoveKillFlags), AA(C->AA),
-        LIS(C->LIS), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU) {}
+        LIS(C->LIS), SchedImpl(std::move(S)) {}
 
   // Provide a vtable anchor
   ~ScheduleDAGMI() override;
 
   /// If this method returns true, handling of the scheduling regions
   /// themselves (in case of a scheduling boundary in MBB) will be done
   /// beginning with the topmost region of MBB.
   bool doMBBSchedRegionsTopDown() const override {
public:
   /// building and before MachineSchedStrategy initialization.
   ///
   /// ScheduleDAGMI takes ownership of the Mutation object.
   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
     if (Mutation)
       Mutations.push_back(std::move(Mutation));
   }
 
-  /// True if an edge can be added from PredSU to SuccSU without creating
-  /// a cycle.
-  bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
-
-  /// Add a DAG edge to the given SU with the given predecessor
-  /// dependence data.
-  ///
-  /// \returns true if the edge may be added without creating a cycle OR if an
-  /// equivalent edge already existed (false indicates failure).
-  bool addEdge(SUnit *SuccSU, const SDep &PredDep);
-
   MachineBasicBlock::iterator top() const { return CurrentTop; }
   MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
 
   /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
   /// region. This covers all instructions in a block, while schedule() may only
   /// cover a subset.
   void enterRegion(MachineBasicBlock *bb,
                    MachineBasicBlock::iterator begin,

llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h

protected:
     /// Adds barrier chain edges from all SUs in map with higher NodeNums than
     /// this new BarrierChain, and remove them from map. It is assumed
     /// BarrierChain has been set before calling this.
     void insertBarrierChain(Value2SUsMap &map);
 
     /// For an unanalyzable memory access, this Value is used in maps.
     UndefValue *UnknownValue;
 
+    /// Topo - A topological ordering for SUnits which permits fast IsReachable
+    /// and similar queries.
+    ScheduleDAGTopologicalSort Topo;
+
     using DbgValueVector =
         std::vector<std::pair<MachineInstr *, MachineInstr *>>;
     /// Remember instruction that precedes DBG_VALUE.
     /// These are generated by buildSchedGraph but persist so they can be
     /// referenced when emitting the final schedule.
     DbgValueVector DbgValues;
     MachineInstr *FirstDbgValue = nullptr;
 
public:
     std::string getGraphNodeLabel(const SUnit *SU) const override;
 
     /// Returns a label for the region of code covered by the DAG.
     std::string getDAGName() const override;
 
     /// Fixes register kill flags that scheduling has made invalid.
     void fixupKills(MachineBasicBlock &MBB);
 
+    /// True if an edge can be added from PredSU to SuccSU without creating
+    /// a cycle.
+    bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
+
+    /// Add a DAG edge to the given SU with the given predecessor
+    /// dependence data.
+    ///
+    /// \returns true if the edge may be added without creating a cycle OR if an
+    /// equivalent edge already existed (false indicates failure).
+    bool addEdge(SUnit *SuccSU, const SDep &PredDep);
+
   protected:
     void initSUnits();
     void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx);
     void addPhysRegDeps(SUnit *SU, unsigned OperIdx);
     void addVRegDefDeps(SUnit *SU, unsigned OperIdx);
     void addVRegUseDeps(SUnit *SU, unsigned OperIdx);
 
     /// Initializes register live-range state for updating kills.

llvm/lib/CodeGen/MachineScheduler.cpp

 // ScheduleDAGMI - Basic machine instruction scheduling. This is
 // independent of PreRA/PostRA scheduling and involves no extra book-keeping for
 // virtual registers.
 // ===----------------------------------------------------------------------===/
 
 // Provide a vtable anchor.
 ScheduleDAGMI::~ScheduleDAGMI() = default;
 
-bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
-  return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
-}
-
-bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) {
-  if (SuccSU != &ExitSU) {
-    // Do not use WillCreateCycle, it assumes SD scheduling.
-    // If Pred is reachable from Succ, then the edge creates a cycle.
-    if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
-      return false;
-    Topo.AddPred(SuccSU, PredDep.getSUnit());
-  }
-  SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
-  // Return true regardless of whether a new edge needed to be inserted.
-  return true;
-}
-
 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
 /// NumPredsLeft reaches zero, release the successor node.
 ///
 /// FIXME: Adjust SuccSU height based on MinLatency.
 void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
   SUnit *SuccSU = SuccEdge->getSUnit();
 
   if (SuccEdge->isWeak()) {

 /// scheduling and potentially other custom schedulers.
 void ScheduleDAGMI::schedule() {
   LLVM_DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");
   LLVM_DEBUG(SchedImpl->dumpPolicy());
 
   // Build the DAG.
   buildSchedGraph(AA);
 
-  Topo.InitDAGTopologicalSorting();
-
   postprocessDAG();
 
   SmallVector<SUnit*, 8> TopRoots, BotRoots;
   findRootsAndBiasEdges(TopRoots, BotRoots);
 
   LLVM_DEBUG(dump());
   if (PrintDAGs) dump();
   if (ViewMISchedDAGs) viewGraph();

 /// scheduling algorithm. However, if a scheduler further subclasses
 /// ScheduleDAGMILive then it will want to override this virtual method in order
 /// to update any specialized state.
 void ScheduleDAGMILive::schedule() {
   LLVM_DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");
   LLVM_DEBUG(SchedImpl->dumpPolicy());
   buildDAGWithRegPressure();
 
-  Topo.InitDAGTopologicalSorting();
-
   postprocessDAG();
 
   SmallVector<SUnit*, 8> TopRoots, BotRoots;
   findRootsAndBiasEdges(TopRoots, BotRoots);
 
   // Initialize the strategy before modifying the DAG.
   // This may initialize a DFSResult to be used for queue priority.
   SchedImpl->initialize(this);

 public:
   BaseMemOpClusterMutation(const TargetInstrInfo *tii,
                            const TargetRegisterInfo *tri, bool IsLoad)
       : TII(tii), TRI(tri), IsLoad(IsLoad) {}
 
   void apply(ScheduleDAGInstrs *DAGInstrs) override;
 
 protected:
-  void clusterNeighboringMemOps(ArrayRef<SUnit *> MemOps, ScheduleDAGMI *DAG);
+  void clusterNeighboringMemOps(ArrayRef<SUnit *> MemOps,
+                                ScheduleDAGInstrs *DAG);
 };
 
 class StoreClusterMutation : public BaseMemOpClusterMutation {
 public:
   StoreClusterMutation(const TargetInstrInfo *tii,
                        const TargetRegisterInfo *tri)
       : BaseMemOpClusterMutation(tii, tri, false) {}
 };
createStoreClusterDAGMutation(const TargetInstrInfo *TII,
                               const TargetRegisterInfo *TRI) {
   return EnableMemOpCluster ? llvm::make_unique<StoreClusterMutation>(TII, TRI)
                             : nullptr;
 }
 
 } // end namespace llvm
 
 void BaseMemOpClusterMutation::clusterNeighboringMemOps(
-    ArrayRef<SUnit *> MemOps, ScheduleDAGMI *DAG) {
+    ArrayRef<SUnit *> MemOps, ScheduleDAGInstrs *DAG) {
   SmallVector<MemOpInfo, 32> MemOpRecords;
   for (SUnit *SU : MemOps) {
     MachineOperand *BaseOp;
     int64_t Offset;
     if (TII->getMemOperandWithOffset(*SU->getInstr(), BaseOp, Offset, TRI))
       MemOpRecords.push_back(MemOpInfo(SU, BaseOp, Offset));
   }
   if (MemOpRecords.size() < 2)
if (TII->shouldClusterMemOps(*MemOpRecords[Idx].BaseOp,
       }
       ++ClusterLength;
     } else
       ClusterLength = 1;
   }
 }
 
 /// Callback from DAG postProcessing to create cluster edges for loads.
-void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAGInstrs) {
-  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
-
+void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAG) {
   // Map DAG NodeNum to store chain ID.
   DenseMap<unsigned, unsigned> StoreChainIDs;
   // Map each store chain to a set of dependent MemOps.
   SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents;
   for (SUnit &SU : DAG->SUnits) {
     if ((IsLoad && !SU.getInstr()->mayLoad()) ||
         (!IsLoad && !SU.getInstr()->mayStore()))
       continue;

llvm/lib/CodeGen/MacroFusion.cpp

 
 static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden,
   cl::desc("Enable scheduling for macro fusion."), cl::init(true));
 
 static bool isHazard(const SDep &Dep) {
   return Dep.getKind() == SDep::Anti || Dep.getKind() == SDep::Output;
 }
 
-static bool fuseInstructionPair(ScheduleDAGMI &DAG, SUnit &FirstSU,
+static bool fuseInstructionPair(ScheduleDAGInstrs &DAG, SUnit &FirstSU,
                                 SUnit &SecondSU) {
   // Check that neither instr is already paired with another along the edge
   // between them.
   for (SDep &SI : FirstSU.Succs)
     if (SI.isCluster())
       return false;
 
   for (SDep &SI : SecondSU.Preds)
     if (SI.isCluster())
       return false;
   // Though the reachability checks above could be made more generic,
-  // perhaps as part of ScheduleDAGMI::addEdge(), since such edges are valid,
-  // the extra computation cost makes it less interesting in general cases.
+  // perhaps as part of ScheduleDAGInstrs::addEdge(), since such edges are
+  // valid, the extra computation cost makes it less interesting in general
+  // cases.
 
   // Create a single weak edge between the adjacent instrs. The only effect is
   // to cause bottom-up scheduling to heavily prioritize the clustered instrs.
   if (!DAG.addEdge(&SecondSU, SDep(&FirstSU, SDep::Cluster)))
     return false;
 
   // Adjust the latency between both instrs.
   for (SDep &SI : FirstSU.Succs)

 
 namespace {
 
 /// Post-process the DAG to create cluster edges between instrs that may
 /// be fused by the processor into a single operation.
 class MacroFusion : public ScheduleDAGMutation {
   ShouldSchedulePredTy shouldScheduleAdjacent;
   bool FuseBlock;
-  bool scheduleAdjacentImpl(ScheduleDAGMI &DAG, SUnit &AnchorSU);
+  bool scheduleAdjacentImpl(ScheduleDAGInstrs &DAG, SUnit &AnchorSU);
 
 public:
   MacroFusion(ShouldSchedulePredTy shouldScheduleAdjacent, bool FuseBlock)
     : shouldScheduleAdjacent(shouldScheduleAdjacent), FuseBlock(FuseBlock) {}
 
   void apply(ScheduleDAGInstrs *DAGInstrs) override;
 };
 
 } // end anonymous namespace
 
-void MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
-  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
-
+void MacroFusion::apply(ScheduleDAGInstrs *DAG) {
   if (FuseBlock)
     // For each of the SUnits in the scheduling block, try to fuse the instr in
     // it with one in its predecessors.
     for (SUnit &ISU : DAG->SUnits)
         scheduleAdjacentImpl(*DAG, ISU);
 
   if (DAG->ExitSU.getInstr())
     // Try to fuse the instr in the ExitSU with one in its predecessors.
     scheduleAdjacentImpl(*DAG, DAG->ExitSU);
 }
 
 /// Implement the fusion of instr pairs in the scheduling DAG,
 /// anchored at the instr in AnchorSU..
-bool MacroFusion::scheduleAdjacentImpl(ScheduleDAGMI &DAG, SUnit &AnchorSU) {
+bool MacroFusion::scheduleAdjacentImpl(ScheduleDAGInstrs &DAG,
+                                       SUnit &AnchorSU) {
   const MachineInstr &AnchorMI = *AnchorSU.getInstr();
   const TargetInstrInfo &TII = *DAG.TII;
   const TargetSubtargetInfo &ST = DAG.MF.getSubtarget();
 
   // Check if the anchor instr may be fused.
   if (!shouldScheduleAdjacent(TII, ST, nullptr, AnchorMI))
     return false;
 

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

 #endif
 }
 
 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
                                      const MachineLoopInfo *mli,
                                      bool RemoveKillFlags)
     : ScheduleDAG(mf), MLI(mli), MFI(mf.getFrameInfo()),
       RemoveKillFlags(RemoveKillFlags),
-      UnknownValue(UndefValue::get(
-                             Type::getVoidTy(mf.getFunction().getContext()))) {
+      UnknownValue(
+          UndefValue::get(Type::getVoidTy(mf.getFunction().getContext()))),
+      Topo(SUnits, &ExitSU) {
   DbgValues.clear();
 
   const TargetSubtargetInfo &ST = mf.getSubtarget();
   SchedModel.init(&ST);
 }
 
 /// If this machine instr has memory reference information and it can be
 /// tracked to a normal reference to a known object, return the Value
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
 
   if (DbgMI)
     FirstDbgValue = DbgMI;
 
   Defs.clear();
   Uses.clear();
   CurrentVRegDefs.clear();
   CurrentVRegUses.clear();
+
+  Topo.InitDAGTopologicalSorting();
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
   PSV->printCustom(OS);
   return OS;
 }
 
 void ScheduleDAGInstrs::Value2SUsMap::dump() {

 }
 
 /// Return the basic block label. It is not necessarilly unique because a block
 /// contains multiple scheduling regions. But it is fine for visualization.
 std::string ScheduleDAGInstrs::getDAGName() const {
   return "dag." + BB->getFullName();
 }
 
+bool ScheduleDAGInstrs::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
+  return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
+}
+
+bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
+  if (SuccSU != &ExitSU) {
+    // Do not use WillCreateCycle, it assumes SD scheduling.
+    // If Pred is reachable from Succ, then the edge creates a cycle.
+    if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
+      return false;
+    Topo.AddPred(SuccSU, PredDep.getSUnit());
+  }
+  SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
+  // Return true regardless of whether a new edge needed to be inserted.
+  return true;
+}
+
 //===----------------------------------------------------------------------===//
 // SchedDFSResult Implementation
 //===----------------------------------------------------------------------===//
 
 namespace llvm {
 
 /// Internal state used to compute SchedDFSResult.
 class SchedDFSImpl {

llvm/lib/Target/AMDGPU/AMDGPUSubtarget.cpp

 }
 
 namespace {
 struct MemOpClusterMutation : ScheduleDAGMutation {
   const SIInstrInfo *TII;
 
   MemOpClusterMutation(const SIInstrInfo *tii) : TII(tii) {}
 
-  void apply(ScheduleDAGInstrs *DAGInstrs) override {
-    ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
-
+  void apply(ScheduleDAGInstrs *DAG) override {
     SUnit *SUa = nullptr;
     // Search for two consequent memory operations and link them
     // to prevent scheduler from moving them apart.
     // In DAG pre-process SUnits are in the original order of
     // the instructions before scheduling.
     for (SUnit &SU : DAG->SUnits) {
       MachineInstr &MI2 = *SU.getInstr();
       if (!MI2.mayLoad() && !MI2.mayStore()) {

llvm/lib/Target/X86/X86Subtarget.h

bool enableIndirectBrExpand() const override {
     return useRetpolineIndirectBranches();
   }
 
   /// Enable the MachineScheduler pass for all X86 subtargets.
   bool enableMachineScheduler() const override { return true; }
 
   bool enableEarlyIfConversion() const override;
 
+  void getPostRAMutations(
+      std::vector<std::unique_ptr<ScheduleDAGMutation>> &Mutations) const;
+
   AntiDepBreakMode getAntiDepBreakMode() const override {
     return TargetSubtargetInfo::ANTIDEP_CRITICAL;
   }
 
   bool enableAdvancedRASplitCost() const override { return true; }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_X86_X86SUBTARGET_H

llvm/lib/Target/X86/X86Subtarget.cpp

 //===-- X86Subtarget.cpp - X86 Subtarget Information ----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the X86 specific subclass of TargetSubtargetInfo.
 //
 //===----------------------------------------------------------------------===//
 
 #include "X86.h"
 
 #include "X86CallLowering.h"
 #include "X86LegalizerInfo.h"
+#include "X86MacroFusion.h"
 #include "X86RegisterBankInfo.h"
 #include "X86Subtarget.h"
 #include "MCTargetDesc/X86BaseInfo.h"
 #include "X86TargetMachine.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
 #include "llvm/CodeGen/GlobalISel/InstructionSelect.h"
 #include "llvm/IR/Attributes.h"

 
 const RegisterBankInfo *X86Subtarget::getRegBankInfo() const {
   return RegBankInfo.get();
 }
 
 bool X86Subtarget::enableEarlyIfConversion() const {
   return hasCMov() && X86EarlyIfConv;
 }
+
+void X86Subtarget::getPostRAMutations(
+    std::vector<std::unique_ptr<ScheduleDAGMutation>> &Mutations) const {
+  Mutations.push_back(createX86MacroFusionDAGMutation());
+}