[CodeGen] Move MacroFusion to the target

[evandro]

Summary

This patch moves the class for scheduling adjacent instructions, MacroFusion, to the target.

In AArch64, it also expands the fusion to all instructions pairs in a scheduling block, beyond just among the predecessors of the branch at the end.

[MatzeB]

Have you checked the effects for compiletime? This will check every edge in the schedule graph, I wonder if we shouldn't rather delegate the whole search to the target so it can restrict this to the actually interesting instructions instead of checking every edge.

[evandro]

In D28489#640575, @MatzeB wrote:

Have you checked the effects for compiletime? This will check every edge in the schedule graph, I wonder if we shouldn't rather delegate the whole search to the target so it can restrict this to the actually interesting instructions instead of checking every edge.

At least on a rather fast x86 machine, any difference in the compile time was buried below the noise level.

[MatzeB]

And just to warn you because I am currently running into these issues: The current macrofusion code fails to work properly for nodes having around the pending queue (which mostly means macrofusion often failing for post-ra schedulers).
If there are no post-ra schedulers on the other hand the register allocator sometimes places copy, spill, reload instructions in between.

I am currently working on patches that form instruction bundles out of macrofusion opportunities, unfortunately this is coming along slowly as instruction bundles pre-ra are not a commonly used feature.

[evandro]

In D28489#640596, @MatzeB wrote:

If there are no post-ra schedulers on the other hand the register allocator sometimes places copy, spill, reload instructions in between.

Yes, I noticed such irritating occurrences.

[atrick]

Would it make sense to have a TII.mayFuseWithPrecedingInstr() to avoid testing all DAG edges? The DAG is quadratic, but this a rare opportunity.

[MatzeB]

In D28489#640628, @atrick wrote:

Would it make sense to have a TII.mayFuseWithPrecedingInstr() to avoid testing all DAG edges? The DAG is quadratic, but this a rare opportunity.

Or let targets subclass or write their own scheduledag mutation with an apropriate search strategy instead of the TII callback?

[atrick]

Yep, this could all be done in the target. SDep::Cluster is effectively a scheduler API for the subtarget to use as it wishes.

On the other hand, that just pushes the problem to the target code, and this is proposed for AArch64.

[evandro]

Pardon my cluelessness, but are you guys on a tangent? I'm truly confused.

[evandro]

Ping^1

[atrick]

I think you should find a way to do this without calling shouldScheduleAdjacent on every DAG node. It's fine to say you've tested compilation time but what really matters here are the pathological cases with very large blocks. It's rare for instructions in the middle of blocks to have fusion opportunities, so it's wrong to introduce this potential cost for all blocks.

[evandro]

I have other patches in the line that depend on this one which fuse other pairs of instrs (e.g., D28698) that do happen in the middle of blocks.

But I understand your point. An alternative that I considered before was through TargetSubtargetInfo::adjustSchedDependency(). Thoughts?

[atrick]

Note that adjustSchedDependency is defined as updating the latency. It's very important for target hooks not to mutate data structures people's backs.

I think I see @MatzeB's point. Just remove MacroFusion from the target independent MachineScheduler. Code reuse is not really helpful here. X86 should just have it's own MacroFusion, as with AArch64. The still register the SchedDAGMutation the same way.

• Remove shouldScheduleAdjacent from TargetInstrInfo. Targets can define that helper locally.

• X86 MacroFusion doesn't change at all. The code just moves.

• In AArch64 MacroFusion, *before* checking the edge, determine if if this opcode wants to be fused (e.g. isi it MOVK). Only the edges leading to fusable intrustrions are checked. No need to go through a TargetInstrInfo virtual call.

[evandro]

Just the skeleton of MacroFusion was left behind. If anything, in order to leave the option misched-fusion intact and to keep the interface using createMacroFusionDAGMutation().

[MatzeB]

The targets add the DAG Mutators anyway, so you should be able to remove the whole shouldScheduleAdjacent() callback let the targets define their own class MacroFusion : public ScheduleDAGMutation { ... } class which they then add as a mutator.

[MatzeB]

In D28489#659179, @MatzeB wrote:

The targets add the DAG Mutators anyway, so you should be able to remove the whole shouldScheduleAdjacent() callback let the targets define their own class MacroFusion : public ScheduleDAGMutation { ... } class which they then add as a mutator.

That would also mean to get rid of the createMacroFusionDAGMutation(const TargetInstrInfo *TII) function and thereby the EnableMacroFusion flag. This is fine IMO as on AArch64 you can just as well enable/disable it with the FeatureArithmeticBccFusion/FeatureArithmeticCbzFusion.

[evandro]

@MatzeB,

I just thought that it was convenient to control MacroFusion with a global option, misched-fusion, regardless of what the target prefers.

[MatzeB]

In D28489#659194, @evandro wrote:

@MatzeB,

I just thought that it was convenient to control MacroFusion with a global option, misched-fusion, regardless of what the target prefers.

I don't think a global flag is worth adding a callback and extra functions to MachineScheduler. I don't think there is that much value in the flag to justify that esp. since you can do -mattr=-FeatureArithmeticBccFusion,-FeatureArithmeticCbzFusion as well.

[MatzeB]

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

2054–2063

This code could be put directly in AArch64MacroFusion::apply(). The same comment applies to the X86 version.

llvm/lib/Target/AArch64/AArch64MacroFusion.h

26–35 ↗

(On Diff #86350)

This can stay private to the .cpp file where createMacroFusionDAGMutation() is defined and doesn't need to go into a header.

The same comment applies to the X86 version.

llvm/test/CodeGen/AArch64/misched-fusion.ll

10–19 ↗

(On Diff #86350)

Why is there a testcase change, shoulnd't this be NFC?

[evandro]

llvm/test/CodeGen/AArch64/misched-fusion.ll

10–19 ↗

(On Diff #86350)

Since I made it common for iOS and Linux (v. line 4), I meant to trim the check to the germane part.

[MatzeB]

llvm/test/CodeGen/AArch64/misched-fusion.ll

10–19 ↗

(On Diff #86350)

makes sense

[evandro]

llvm/lib/Target/AArch64/AArch64MacroFusion.h

26–35 ↗

(On Diff #86350)

You mean moving the method scheduleAdjacent() from <Target>InstrInfo to <Target>MacroFusion as a private function?

[MatzeB]

llvm/lib/Target/AArch64/AArch64MacroFusion.h

26–35 ↗

(On Diff #86350)

Pretty much. After moving the method you will probably realize that there the only caller is inside apply() and the apply() method consists only of that 1 call, so you can just as well "inline" manually and move the code into the apply() method.

[MatzeB]

LGTM with nitpicks addressed:

llvm/lib/Target/AArch64/AArch64MacroFusion.cpp

10 ↗

(On Diff #86373)

Should be /// \file This file ...

191 ↗

(On Diff #86373)

No space before ().

195 ↗

(On Diff #86373)

Should be // end namespace llvm according to coding standards.

llvm/lib/Target/AArch64/AArch64MacroFusion.h

10 ↗

(On Diff #86373)

Should be /// \file This file ...

24–31 ↗

(On Diff #86373)

Please move the class declaration into the AArch64MacroFusion.cpp file and into an anonymous namespace.

llvm/lib/Target/X86/X86MacroFusion.cpp

10 ↗

(On Diff #86373)

Should be /// \file ...

245 ↗

(On Diff #86373)

No space before ()

249 ↗

(On Diff #86373)

Should be // end namespace llvm.

llvm/lib/Target/X86/X86MacroFusion.h

10 ↗

(On Diff #86373)

Should be /// \file This file ...

24–31 ↗

(On Diff #86373)

Please move the class declaration into the X86MacroFusion.cpp file and into an anonymous namespace.

[evandro]

Final patch after approval.

[chapuni]

Usings of \param are improper. Tweaked in r293744 just to eliminate \param(s).

\param takes at least two parameters.

\param NAME Description...

You may write \param(s) like,

/// \brief Verify that the instruction pair, should be scheduled back to back.
/// \param First The first MI to verify
/// \param Second The second MI

Note, trunk clang doesn't recognize like "\param First,Second".

llvm/trunk/lib/Target/AArch64/AArch64MacroFusion.cpp

29 ↗

(On Diff #86556)

First and Second

123 ↗

(On Diff #86556)

DAG, ASU, and Preds

llvm/trunk/lib/Target/X86/X86MacroFusion.cpp

29 ↗

(On Diff #86556)

First and Second

[evandro]

Thank you, @chapuni.

llvm/include/llvm/Target/TargetInstrInfo.h

 class MDNode;
 class MCInst;
 struct MCSchedModel;
 class MCSymbolRefExpr;
 class SDNode;
 class ScheduleHazardRecognizer;
 class SelectionDAG;
 class ScheduleDAG;
+class ScheduleDAGInstrs;
 class TargetRegisterClass;
 class TargetRegisterInfo;
 class TargetSubtargetInfo;
 class TargetSchedModel;
 class DFAPacketizer;
 
 template<class T> class SmallVectorImpl;
 
public:
   ///   DAG->addMutation(createStoreClusterDAGMutation(DAG->TII, DAG->TRI));
   /// to TargetPassConfig::createMachineScheduler() to have an effect.
   virtual bool shouldClusterMemOps(MachineInstr &FirstLdSt,
                                    MachineInstr &SecondLdSt,
                                    unsigned NumLoads) const {
     llvm_unreachable("target did not implement shouldClusterMemOps()");
   }
 
-  /// Can this target fuse the given instructions if they are scheduled
-  /// adjacent. Note that you have to add:
+  /// Override the fusion of instructions in the given scheduling block.
+  /// Note that you have to add:
   ///   DAG.addMutation(createMacroFusionDAGMutation());
   /// to TargetPassConfig::createMachineScheduler() to have an effect.
-  virtual bool shouldScheduleAdjacent(const MachineInstr &First,
-                                      const MachineInstr &Second) const {
-    llvm_unreachable("target did not implement shouldScheduleAdjacent()");
+  virtual void scheduleAdjacent(ScheduleDAGInstrs *DAGInstrs) const {
+    llvm_unreachable("target did not implement scheduleAdjacent()");
   }
 
   /// Reverses the branch condition of the specified condition list,
   /// returning false on success and true if it cannot be reversed.
   virtual
   bool reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
     return true;
   }

llvm/lib/CodeGen/MachineScheduler.cpp

 /// \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;
 public:
   MacroFusion(const TargetInstrInfo &TII)
     : TII(TII) {}
 
-  void apply(ScheduleDAGInstrs *DAGInstrs) override;
+  void apply(ScheduleDAGInstrs *DAGInstrs) override {
+    TII.scheduleAdjacent(DAGInstrs);
+  }
 };
 } // anonymous
 
 namespace llvm {
 
 std::unique_ptr<ScheduleDAGMutation>
 createMacroFusionDAGMutation(const TargetInstrInfo *TII) {
   return EnableMacroFusion ? make_unique<MacroFusion>(*TII) : nullptr;
 }
 
 } // namespace llvm
 
-/// \brief Callback from DAG postProcessing to create cluster edges to encourage
-/// fused operations.
-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 (SDep &PredDep : ExitSU.Preds) {
-    if (PredDep.isWeak())
-      continue;
-    SUnit &SU = *PredDep.getSUnit();
-    MachineInstr &Pred = *SU.getInstr();
-    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(&ExitSU, SDep(&SU, SDep::Cluster));
-    (void)Success;
-    assert(Success && "No DAG nodes should be reachable from ExitSU");
-
-    // Adjust latency of data deps between the nodes.
-    for (SDep &PredDep : ExitSU.Preds) {
-      if (PredDep.getSUnit() == &SU)
-        PredDep.setLatency(0);
-    }
-    for (SDep &SuccDep : SU.Succs) {
-      if (SuccDep.getSUnit() == &ExitSU)
-        SuccDep.setLatency(0);
-    }
-
-    DEBUG(dbgs() << "Macro Fuse SU(" << SU.NodeNum << ")\n");
-    break;
-  }
-}
-
 //===----------------------------------------------------------------------===//
 // CopyConstrain - DAG post-processing to encourage copy elimination.
 //===----------------------------------------------------------------------===//
 
 namespace {
 /// \brief Post-process the DAG to create weak edges from all uses of a copy to
 /// the one use that defines the copy's source vreg, most likely an induction
 /// variable increment.

llvm/lib/Target/AArch64/AArch64InstrInfo.h

public:
 
   bool getMemOpBaseRegImmOfsWidth(MachineInstr &LdSt, unsigned &BaseReg,
                                   int64_t &Offset, unsigned &Width,
                                   const TargetRegisterInfo *TRI) const;
 
   bool shouldClusterMemOps(MachineInstr &FirstLdSt, MachineInstr &SecondLdSt,
                            unsigned NumLoads) const override;
 
-  bool shouldScheduleAdjacent(const MachineInstr &First,
-                              const MachineInstr &Second) const override;
+  void scheduleAdjacent(ScheduleDAGInstrs *DAGInstrs) const override;
 
   MachineInstr *emitFrameIndexDebugValue(MachineFunction &MF, int FrameIx,
                                          uint64_t Offset, const MDNode *Var,
                                          const MDNode *Expr,
                                          const DebugLoc &DL) const;
   void copyPhysRegTuple(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
                         const DebugLoc &DL, unsigned DestReg, unsigned SrcReg,
                         bool KillSrc, unsigned Opcode,

llvm/lib/Target/AArch64/AArch64InstrInfo.cpp

 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/CommandLine.h"
bool AArch64InstrInfo::shouldClusterMemOps(MachineInstr &FirstLdSt,
   if (Offset1 > 63 || Offset1 < -64)
     return false;
 
   // The caller should already have ordered First/SecondLdSt by offset.
   assert(Offset1 <= Offset2 && "Caller should have ordered offsets.");
   return Offset1 + 1 == Offset2;
 }
 
-bool AArch64InstrInfo::shouldScheduleAdjacent(
-    const MachineInstr &First, const MachineInstr &Second) const {
-  if (Subtarget.hasArithmeticBccFusion()) {
+/// \brief Verify that the instruction pair, \param First and \param Second,
+/// should be scheduled back to back.  Given an anchor instruction, if the other
+/// instruction is unspecified, then verify that the anchor instruction may be
+/// part of a pair at all.
+static bool shouldScheduleAdjacent(const AArch64InstrInfo &TII,
+                                   const AArch64Subtarget &ST,
+                                   const MachineInstr *First,
+                                   const MachineInstr *Second) {
+  unsigned FirstOpcode = First ?
+                         First->getOpcode() : AArch64::INSTRUCTION_LIST_END;
+  unsigned SecondOpcode = Second ?
+                          Second->getOpcode() : AArch64::INSTRUCTION_LIST_END;
+
+  if (ST.hasArithmeticBccFusion())
     // Fuse CMN, CMP, TST followed by Bcc.
-    unsigned SecondOpcode = Second.getOpcode();
-    if (SecondOpcode == AArch64::Bcc) {
-      switch (First.getOpcode()) {
+    if (SecondOpcode == AArch64::Bcc)
+      switch (FirstOpcode) {
       default:
         return false;
       case AArch64::ADDSWri:
       case AArch64::ADDSWrr:
       case AArch64::ADDSXri:
       case AArch64::ADDSXrr:
       case AArch64::ANDSWri:
       case AArch64::ANDSWrr:
if (SecondOpcode == AArch64::Bcc)
       case AArch64::ADDSXrs:
       case AArch64::ANDSWrs:
       case AArch64::ANDSXrs:
       case AArch64::SUBSWrs:
       case AArch64::SUBSXrs:
       case AArch64::BICSWrs:
       case AArch64::BICSXrs:
         // Shift value can be 0 making these behave like the "rr" variant...
-        return !hasShiftedReg(Second);
-      }
-    }
+        return !TII.hasShiftedReg(*First);
+      case AArch64::INSTRUCTION_LIST_END:
+        return true;
       }
-  if (Subtarget.hasArithmeticCbzFusion()) {
+
+  if (ST.hasArithmeticCbzFusion())
     // Fuse ALU operations followed by CBZ/CBNZ.
-    unsigned SecondOpcode = Second.getOpcode();
     if (SecondOpcode == AArch64::CBNZW || SecondOpcode == AArch64::CBNZX ||
-        SecondOpcode == AArch64::CBZW || SecondOpcode == AArch64::CBZX) {
-      switch (First.getOpcode()) {
+        SecondOpcode == AArch64::CBZW || SecondOpcode == AArch64::CBZX)
+      switch (FirstOpcode) {
       default:
         return false;
       case AArch64::ADDWri:
       case AArch64::ADDWrr:
       case AArch64::ADDXri:
       case AArch64::ADDXrr:
       case AArch64::ANDWri:
       case AArch64::ANDWrr:
if (SecondOpcode == AArch64::CBNZW || SecondOpcode == AArch64::CBNZX ||
       case AArch64::ADDXrs:
       case AArch64::ANDWrs:
       case AArch64::ANDXrs:
       case AArch64::SUBWrs:
       case AArch64::SUBXrs:
       case AArch64::BICWrs:
       case AArch64::BICXrs:
         // Shift value can be 0 making these behave like the "rr" variant...
-        return !hasShiftedReg(Second);
+        return !TII.hasShiftedReg(*First);
+      case AArch64::INSTRUCTION_LIST_END:
+        return true;
       }
-    }
+
+  return false;
+
+/// \brief Implement the fusion of instruction pairs in the scheduling
+/// \param DAG, anchored at the instruction in \param ASU. \param Preds
+/// indicates if its dependencies in \param APreds are predecessors instead of
+/// successors.
+static bool scheduleAdjacentImpl(const AArch64InstrInfo &TII,
+                                 const AArch64Subtarget &ST,
+                                 ScheduleDAGMI *DAG, SUnit *ASU,
+                                 SmallVectorImpl<SDep> &APreds, bool Preds) {
+  const MachineInstr *AMI = ASU->getInstr();
+  if (!AMI || AMI->isPseudo() || AMI->isTransient() ||
+      (Preds && !shouldScheduleAdjacent(TII, ST, nullptr, AMI)) ||
+      (!Preds && !shouldScheduleAdjacent(TII, ST, AMI, nullptr)))
+    return false;
+
+  for (SDep &BDep : APreds) {
+    if (BDep.isWeak())
+      continue;
+
+    SUnit *BSU = BDep.getSUnit();
+    const MachineInstr *BMI = BSU->getInstr();
+    if (!BMI || BMI->isPseudo() || BMI->isTransient() ||
+        (Preds && !shouldScheduleAdjacent(TII, ST, BMI, AMI)) ||
+        (!Preds && !shouldScheduleAdjacent(TII, ST, AMI, BMI)))
+      continue;
+
+    // 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 (Preds)
+      DAG->addEdge(ASU, SDep(BSU, SDep::Cluster));
+    else
+      DAG->addEdge(BSU, SDep(ASU, SDep::Cluster));
+
+    // Adjust the latency between the 1st instr and its predecessors/successors.
+    for (SDep &Dep : APreds)
+      if (Dep.getSUnit() == BSU)
+        Dep.setLatency(0);
+
+    // Adjust the latency between the 2nd instr and its successors/predecessors.
+    auto &BSuccs = Preds ? BSU->Succs : BSU->Preds;
+    for (SDep &Dep : BSuccs)
+      if (Dep.getSUnit() == ASU)
+        Dep.setLatency(0);
+
+    return true;
   }
+
   return false;
 }
 
+/// \brief Callback from DAG postProcessing to create cluster edges to encourage
+/// fused operations.
+void
+AArch64InstrInfo::scheduleAdjacent(ScheduleDAGInstrs *DAGInstrs) const {
+  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
+
+  // For each of the SUnits in the scheduling block, try to fuse the instruction
+  // in it with one in its successors.
+  for (SUnit &ASU : DAG->SUnits)
+    scheduleAdjacentImpl(*this, Subtarget, DAG, &ASU, ASU.Succs, false);
+
+  // Try to fuse the instruction in the ExitSU with one in its predecessors.
+  scheduleAdjacentImpl(*this, Subtarget,
+                       DAG, &DAG->ExitSU, DAG->ExitSU.Preds, true);
+}
+
 MachineInstr *AArch64InstrInfo::emitFrameIndexDebugValue(
     MachineFunction &MF, int FrameIx, uint64_t Offset, const MDNode *Var,
     const MDNode *Expr, const DebugLoc &DL) const {
   MachineInstrBuilder MIB = BuildMI(MF, DL, get(AArch64::DBG_VALUE))
                                 .addFrameIndex(FrameIx)
                                 .addImm(0)
                                 .addImm(Offset)
                                 .addMetadata(Var)

llvm/lib/Target/X86/X86InstrInfo.h

public:
   /// together. This function takes two integers that represent the load offsets
   /// from the common base address. It returns true if it decides it's desirable
   /// to schedule the two loads together. "NumLoads" is the number of loads that
   /// have already been scheduled after Load1.
   bool shouldScheduleLoadsNear(SDNode *Load1, SDNode *Load2,
                                int64_t Offset1, int64_t Offset2,
                                unsigned NumLoads) const override;
 
-  bool shouldScheduleAdjacent(const MachineInstr &First,
-                              const MachineInstr &Second) const override;
+  void scheduleAdjacent(ScheduleDAGInstrs *DAGInstrs) const override;
 
   void getNoopForMachoTarget(MCInst &NopInst) const override;
 
   bool
   reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const override;
 
   /// isSafeToMoveRegClassDefs - Return true if it's safe to move a machine
   /// instruction that defines the specified register class.

llvm/lib/Target/X86/X86InstrInfo.cpp

 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineScheduler.h"
 #include "llvm/CodeGen/StackMaps.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/CommandLine.h"
case MVT::f64:
     if (NumLoads)
       return false;
     break;
   }
 
   return true;
 }
 
-bool X86InstrInfo::shouldScheduleAdjacent(const MachineInstr &First,
-                                          const MachineInstr &Second) const {
+/// \brief Verify that the instruction pair, \param First and \param Second,
+/// should be scheduled back to back.  If either instruction is unspecified,
+/// then verify that the other instruction may be part of a pair at all.
+static bool shouldScheduleAdjacent(const X86Subtarget &Subtarget,
+                                   const MachineInstr *First,
+                                   const MachineInstr *Second) {
   // Check if this processor supports macro-fusion. Since this is a minor
   // heuristic, we haven't specifically reserved a feature. hasAVX is a decent
   // proxy for SandyBridge+.
   if (!Subtarget.hasAVX())
     return false;
 
   enum {
     FuseTest,
     FuseCmp,
     FuseInc
   } FuseKind;
 
-  switch (Second.getOpcode()) {
+  unsigned FirstOpcode = First ?
+                         First->getOpcode() : X86::INSTRUCTION_LIST_END;
+  unsigned SecondOpcode = Second ?
+                          Second->getOpcode() : X86::INSTRUCTION_LIST_END;
+
+  switch (SecondOpcode) {
   default:
     return false;
   case X86::JE_1:
   case X86::JNE_1:
   case X86::JL_1:
   case X86::JLE_1:
   case X86::JG_1:
   case X86::JGE_1:
static bool shouldScheduleAdjacent(const X86Subtarget &Subtarget,
   case X86::JNS_1:
   case X86::JP_1:
   case X86::JNP_1:
   case X86::JO_1:
   case X86::JNO_1:
     FuseKind = FuseTest;
     break;
   }
-  switch (First.getOpcode()) {
+
+  switch (FirstOpcode) {
   default:
     return false;
   case X86::TEST8rr:
   case X86::TEST16rr:
   case X86::TEST32rr:
   case X86::TEST64rr:
   case X86::TEST8ri:
   case X86::TEST16ri:
static bool shouldScheduleAdjacent(const X86Subtarget &Subtarget,
   case X86::INC32r:
   case X86::INC64r:
   case X86::INC8r:
   case X86::DEC16r:
   case X86::DEC32r:
   case X86::DEC64r:
   case X86::DEC8r:
     return FuseKind == FuseInc;
+  case X86::INSTRUCTION_LIST_END:
+    return true;
+  }
+}
+
+void X86InstrInfo::scheduleAdjacent(ScheduleDAGInstrs *DAGInstrs) const {
+  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 (!shouldScheduleAdjacent(Subtarget, nullptr, Branch))
+    return;
+
+  for (SDep &PredDep : ExitSU.Preds) {
+    if (PredDep.isWeak())
+      continue;
+    SUnit &SU = *PredDep.getSUnit();
+    MachineInstr &Pred = *SU.getInstr();
+    if (!shouldScheduleAdjacent(Subtarget, &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(&ExitSU, SDep(&SU, SDep::Cluster));
+    (void)Success;
+    assert(Success && "No DAG nodes should be reachable from ExitSU");
+
+    // Adjust latency of data deps between the nodes.
+    for (SDep &PredDep : ExitSU.Preds) {
+      if (PredDep.getSUnit() == &SU)
+        PredDep.setLatency(0);
+    }
+    for (SDep &SuccDep : SU.Succs) {
+      if (SuccDep.getSUnit() == &ExitSU)
+        SuccDep.setLatency(0);
+    }
+
+    break;
   }
 }
 
 bool X86InstrInfo::
 reverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
   assert(Cond.size() == 1 && "Invalid X86 branch condition!");
   X86::CondCode CC = static_cast<X86::CondCode>(Cond[0].getImm());
   Cond[0].setImm(GetOppositeBranchCondition(CC));