[CodeGen] Add generic MacroFusion pass.

[fhahn]

Summary

This patch adds a generic MacroFusion pass, that is used on X86 and
AArch64, which both define target-specific shouldScheduleAdjacent
functions. This generic pass should make it easier for other targets to
implement macro fusion and I intend to add macro fusion for ARM shortly.

[evandro]

lib/CodeGen/MacroFusion.cpp

123

How about using the C++11 range based for loop here?

[fhahn]

Use range based for loop

[evandro]

lib/CodeGen/MacroFusion.cpp

124

!SI.getSUnit() seems to be reduntant.

[fhahn]

Remove redundant !SI.getSUnit()

[evandro]

This patch looks fine to me, but @atrick felt that MacroFusion should belong to the target.

[MatzeB]

I will have to look into the details later.

This patch looks fine to me, but @atrick felt that MacroFusion should belong to the target.

I did some of the pushing away from the previous shared macrofusion code in the MachineScheduler. I was mainly opposed at the previous static structure that pushed all macrofusion through a TII callback. This way all targets were force to share the same logic: X86 which only does macrofusion for branches would still need to look at all instructions of the basic block. This change brings this problem back I believe?

Having said that code sharing is of course a good idea. There are obviously pieces of macrofusion that can and should be shared. Some notes on the patch though I haven't read it in too much detail:

• Is there a way to split this into smaller utility functions/classes so X86 can keep just checking the ExitSU for opportunities?
• That target callback really needs some documentation if it is intended to be reused. I find the current behavior where you sometimes call it with SecondMI == nullptr and sometimes you do not confusing; It feels like two interfaces being mixed together in a single function. At the very least this needs some documentation, better yet simplify the interface if possible.

include/llvm/CodeGen/MacroFusion.h

10–13

Should use /// \file

20–22

Isn't this just repeating the \file comment above?

37

// end namespace llvm

lib/CodeGen/MacroFusion.cpp

11–12

Needs three slashes to be recognized by doxygen.

143

no space after function name

[fhahn]

@MatzeB thank you very much for having a look. I've updated the patch and hope that addresses your comments adequately:

• I've added two boolean member variables FuseBlock and FuseExit .

• I've simplified MacroFusion::scheduleAdjacentImpl to only look at predecessors. I think that shouldn't make a difference as the same pairs should be found, just the order they are discovered may be different. @evandro was there a reason why the successors were considered for SUs in a block?

• shouldScheduleAdjacent now only supports specifying both instructions or the second instruction, I had to update the AArch64 implementation to always check the second opcode first, but it was just the order that changed.

[evandro]

In D34144#781159, @fhahn wrote:

• I've simplified MacroFusion::scheduleAdjacentImpl to only look at predecessors. I think that shouldn't make a difference as the same pairs should be found, just the order they are discovered may be different. @evandro was there a reason why the successors were considered for SUs in a block?

If memory serves, I came across some anecdotal instances when not all instructions were visited otherwise. The reason, methinks, is that some instructions are marked in a special manner, like stores and prefetches. So, I had to start with at the successors of the EntrySU and then again at the predecessors of ExitSU to make sure that all instructions in a BB would be visited.

[evandro]

lib/CodeGen/MacroFusion.cpp

55

I'm inclined to agree that this should be enough.

79

I wonder if this should actually be Dep.isData(), since other dependencies probably don't matter to instruction fusion.

[MatzeB]

include/llvm/CodeGen/MacroFusion.h

24–28

You could make SecondMI a reference now to indicate it is never nullptr, also saves you an assert() below.

30–35

How about splitting this into two functions
createBranchMacroFusionDAGMutation() and createMacroFusionDAGMutation() (or similar names) instead of the two bool parameters to make the calling code easier to read?

lib/CodeGen/MacroFusion.cpp

38

DAG cannot be nullptr, so use a reference; Contrary to apply() this is an internal function which we can change easily.

66

Not true anymore.

68–69

I don't think we should have this shortcut:

• AnchorMI == nullptr should only be possible for ExitSU, which we could guard against in apply()
• Hiding isTransient() seems unnecessary.
• Hiding isPseudo() seems bad. I can easily imagine cases where the last instruction of a pseudo expansions fuses with the next instruction.

72–73

Maybe factor out DAG->TII and DAG->MF.getSubTarget() into a variable, it's used two or three times.

78–80

Maybe we should even go for if (Dep.getKind() != Data) at least I can't imagine right now how anti or output dependencies could lead to macrofusion.

84–86

Similar reasoning as above; Except for DepMI == nullptr being a real possibility for the EntrySU which we can hit here, though you may switch to checking for DepSU.isBoundaryNode() insteadof getInstr() == nullptr to make this fact more obvious.

92–125

Extract the part that adds the fusion edge and does the adjustments into a separate function? I could imagine this being of value if it turns out a new target can use a different/special search strategy for finding fusion opportunities.

132

end anonymous namespace

[evandro]

include/llvm/CodeGen/MacroFusion.h

30–35

As a matter of fact, I can only imagine 2 scenarios: one when the whole BB, including its exit, should be examined and another when only the exit should be examined. If so, then a single flag should suffice.

[fhahn]

Thanks again for the feedback!

lib/CodeGen/MacroFusion.cpp

78–80

I think we have to consider Order dependencies as well, because Order dependencies are used between compare and branch instructions, which should be fused on X86.

[MatzeB]

LGTM with the change below:

lib/CodeGen/MacroFusion.cpp

78–80

Odd, I really would have expected a data dependency on the eflags register for X86. Anyway if that isn't the case today, then you should be able to use at least:

if (Dep.getKind() == Anti || Dep.getKind() == Output || Dep.isWeak())
  continue;

then.

[fhahn]

minor comment cleanup

[FlameTop]

Hi.

This change is failing to build on windows buildbots.

http://lab.llvm.org:8011/waterfall?builder=llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast&builder=llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast

C:\PROGRA~2\MICROS~1.0\VC\bin\amd64\cl.exe /nologo /TP -DGTEST_HAS_RTTI=0 -DLLVM_BUILD_GLOBAL_ISEL -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_HAS_EXCEPTIONS=0 -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -DSTDC_CONSTANT_MACROS -DSTDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Ilib\CodeGen -IC:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\lib\CodeGen -Iinclude -IC:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\include /DWIN32 /D_WINDOWS /Zc:inline /Zc:strictStrings /Oi /Zc:rvalueCast /W4 -wd4141 -wd4146 -wd4180 -wd4244 -wd4258 -wd4267 -wd4291 -wd4345 -wd4351 -wd4355 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4800 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4324 -w14062 -we4238 /MD /O2 /Ob2 -UNDEBUG /EHs-c- /GR- /showIncludes /Folib\CodeGen\CMakeFiles\LLVMCodeGen.dir\MacroFusion.cpp.obj /Fdlib\CodeGen\CMakeFiles\LLVMCodeGen.dir\ /FS -c C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\lib\CodeGen\MacroFusion.cpp
C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\lib\CodeGen\MacroFusion.cpp(139): error C2668: 'llvm::make_unique': ambiguous call to overloaded function
C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\include\llvm/ADT/STLExtras.h(939): note: could be 'std::unique_ptr<anonymous-namespace'::MacroFusion,std::default_delete<_Ty>> llvm::make_unique<anonymous-namespace'::MacroFusion,llvm::ShouldSchedulePredTy&,bool>(llvm::ShouldSchedulePredTy &,bool &&)'

with
[
    _Ty=`anonymous-namespace'::MacroFusion
]

C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE\memory(1628): note: or 'std::unique_ptr<anonymous-namespace'::MacroFusion,std::default_delete<_Ty>> std::make_unique<anonymous-namespace'::MacroFusion,llvm::ShouldSchedulePredTy&,bool>(llvm::ShouldSchedulePredTy &,bool &&)' [found using argument-dependent lookup]

with
[
    _Ty=`anonymous-namespace'::MacroFusion
]

C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\lib\CodeGen\MacroFusion.cpp(139): note: while trying to match the argument list '(llvm::ShouldSchedulePredTy, bool)'
C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\lib\CodeGen\MacroFusion.cpp(146): error C2668: 'llvm::make_unique': ambiguous call to overloaded function
C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\include\llvm/ADT/STLExtras.h(939): note: could be 'std::unique_ptr<anonymous-namespace'::MacroFusion,std::default_delete<_Ty>> llvm::make_unique<anonymous-namespace'::MacroFusion,llvm::ShouldSchedulePredTy&,bool>(llvm::ShouldSchedulePredTy &,bool &&)'

with
[
    _Ty=`anonymous-namespace'::MacroFusion
]

C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE\memory(1628): note: or 'std::unique_ptr<anonymous-namespace'::MacroFusion,std::default_delete<_Ty>> std::make_unique<anonymous-namespace'::MacroFusion,llvm::ShouldSchedulePredTy&,bool>(llvm::ShouldSchedulePredTy &,bool &&)' [found using argument-dependent lookup]

with
[
    _Ty=`anonymous-namespace'::MacroFusion
]

C:\Buildbot\Slave\llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast\llvm.src\lib\CodeGen\MacroFusion.cpp(146): note: while trying to match the argument list '(llvm::ShouldSchedulePredTy, bool)'

regards

[fhahn]

I've reverted the change for now, I'll how to figure out why the call to make_unique is ambiguous with the Microsoft compiler.

[Marandil]

http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20141215/249348.html
It seems you need to use llvm::make_unique explicitly, as MSVC tries to use the std variants.

[fhahn]

Re-committed https://reviews.llvm.org/rL305690 and a small fix https://reviews.llvm.org/rL305694

include/llvm/CodeGen/MacroFusion.h

+//===- MacroFusion.h - Macro Fusion ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file contains the definition of the DAG scheduling mutation to
+/// pair instructions back to back.
+//
+//===----------------------------------------------------------------------===//
+
+#include <functional>
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/CodeGen/MachineScheduler.h"
+
+namespace llvm {
+
+/// \brief Check if the instr pair, FirstMI and SecondMI, should be fused
+/// together. Given SecondMI, when FirstMI is unspecified, then check if
+/// SecondMI may be part of a fused pair at all.
+typedef std::function<bool(const TargetInstrInfo &TII,
+                           const TargetSubtargetInfo &TSI,
+                           const MachineInstr *FirstMI,
+                           const MachineInstr &SecondMI)>  ShouldSchedulePredTy;
+
+/// \brief Create a DAG scheduling mutation to pair instructions back to back
+/// for instructions that benefit according to the target-specific
+/// shouldScheduleAdjacent predicate function.
+std::unique_ptr<ScheduleDAGMutation>
+createMacroFusionDAGMutation(ShouldSchedulePredTy shouldScheduleAdjacent);
+
+/// \brief Create a DAG scheduling mutation to pair branch instructions with one
+/// of their predecessors back to back for instructions that benefit according
+/// to the target-specific shouldScheduleAdjacent predicate function.
+std::unique_ptr<ScheduleDAGMutation>
+createBranchMacroFusionDAGMutation(ShouldSchedulePredTy shouldScheduleAdjacent);
+
+} // end namespace llvm

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   MachineScheduler.cpp
   MachineSink.cpp
   MachineSSAUpdater.cpp
   MachineTraceMetrics.cpp
   MachineVerifier.cpp
   PatchableFunction.cpp
   MIRPrinter.cpp
   MIRPrintingPass.cpp
+  MacroFusion.cpp
   OptimizePHIs.cpp
   ParallelCG.cpp
   PeepholeOptimizer.cpp
   PHIElimination.cpp
   PHIEliminationUtils.cpp
   PostRAHazardRecognizer.cpp
   PostRASchedulerList.cpp
   PreISelIntrinsicLowering.cpp

lib/CodeGen/MacroFusion.cpp

+//===- MacroFusion.cpp - Macro Fusion ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file contains the implementation of the DAG scheduling mutation
+/// to pair instructions back to back.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MacroFusion.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Target/TargetInstrInfo.h"
+
+#define DEBUG_TYPE "misched"
+
+STATISTIC(NumFused, "Number of instr pairs fused");
+
+using namespace llvm;
+
+static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden,
+  cl::desc("Enable scheduling for macro fusion."), cl::init(true));
+
+namespace {
+
+static void fuseInstructionPair(ScheduleDAGMI &DAG, SUnit &FirstSU,
+                                SUnit &SecondSU) {
+  // Create a single weak edge between the adjacent instrs. The only effect is
+  // to cause bottom-up scheduling to heavily prioritize the clustered instrs.
+  DAG.addEdge(&SecondSU, SDep(&FirstSU, SDep::Cluster));
+
+  // Adjust the latency between the anchor instr and its
+  // predecessors.
+  for (SDep &IDep : SecondSU.Preds)
+    if (IDep.getSUnit() == &FirstSU)
+      IDep.setLatency(0);
+
+  // Adjust the latency between the dependent instr and its
+  // predecessors.
+  for (SDep &IDep : FirstSU.Succs)
+    if (IDep.getSUnit() == &SecondSU)
+      IDep.setLatency(0);
+
+  DEBUG(dbgs() << DAG.MF.getName() << "(): Macro fuse ";
+        FirstSU.print(dbgs(), &DAG); dbgs() << " - ";
+        SecondSU.print(dbgs(), &DAG); dbgs() << " /  ";
+        dbgs() << DAG.TII->getName(FirstSU.getInstr()->getOpcode()) << " - " <<
+                  DAG.TII->getName(SecondSU.getInstr()->getOpcode()) << '\n'; );
+
+  if (&SecondSU != &DAG.ExitSU)
+    // Make instructions dependent on FirstSU also dependent on SecondSU to
+    // prevent them from being scheduled between FirstSU and and SecondSU.
+    for (const SDep &SI : FirstSU.Succs) {
+      if (SI.getSUnit() == &SecondSU)
+        continue;
+      DEBUG(dbgs() << "  Copy Succ ";
+            SI.getSUnit()->print(dbgs(), &DAG); dbgs() << '\n';);
+      DAG.addEdge(SI.getSUnit(), SDep(&SecondSU, SDep::Artificial));
+    }
+
+  ++NumFused;
+}
+
+
+/// \brief 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);
+
+public:
+  MacroFusion(ShouldSchedulePredTy shouldScheduleAdjacent, bool FuseBlock)
+    : shouldScheduleAdjacent(shouldScheduleAdjacent), FuseBlock(FuseBlock) {}
+
+  void apply(ScheduleDAGInstrs *DAGInstrs) override;
+};
+
+void MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
+  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
+
+  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);
+}
+
+/// \brief Implement the fusion of instr pairs in the scheduling DAG,
+/// anchored at the instr in AnchorSU..
+bool MacroFusion::scheduleAdjacentImpl(ScheduleDAGMI &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;
+
+  // Explorer for fusion candidates among the dependencies of the anchor instr.
+  for (SDep &Dep : AnchorSU.Preds) {
+    // Ignore dependencies that don't enforce ordering.
+    if (Dep.getKind() == SDep::Anti || Dep.getKind() == SDep::Output ||
+        Dep.isWeak())
+      continue;
+
+    SUnit &DepSU = *Dep.getSUnit();
+    if (DepSU.isBoundaryNode())
+      continue;
+
+    const MachineInstr *DepMI = DepSU.getInstr();
+    if (!shouldScheduleAdjacent(TII, ST, DepMI, AnchorMI))
+      continue;
+
+    fuseInstructionPair(DAG, DepSU, AnchorSU);
+    return true;
+  }
+
+  return false;
+}
+
+} // end anonymous namespace
+
+
+namespace llvm {
+
+std::unique_ptr<ScheduleDAGMutation>
+createMacroFusionDAGMutation(ShouldSchedulePredTy shouldScheduleAdjacent) {
+  if(EnableMacroFusion)
+    return make_unique<MacroFusion>(shouldScheduleAdjacent, true);
+  return nullptr;
+}
+
+std::unique_ptr<ScheduleDAGMutation>
+createBranchMacroFusionDAGMutation(ShouldSchedulePredTy shouldScheduleAdjacent) {
+  if(EnableMacroFusion)
+    return make_unique<MacroFusion>(shouldScheduleAdjacent, false);
+  return nullptr;
+}
+
+} // end namespace llvm

lib/Target/AArch64/AArch64MacroFusion.h

 //===- AArch64MacroFusion.h - AArch64 Macro Fusion ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
-// \fileThis file is distributed under the University of Illinois Open Source
+// This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains the AArch64 definition of the DAG scheduling mutation
-// to pair instructions back to back.
+/// \file This file contains the AArch64 definition of the DAG scheduling
+/// mutation to pair instructions back to back.
 //
 //===----------------------------------------------------------------------===//
 
-#include "AArch64InstrInfo.h"
 #include "llvm/CodeGen/MachineScheduler.h"
 
-//===----------------------------------------------------------------------===//
-// AArch64MacroFusion - DAG post-processing to encourage fusion of macro ops.
-//===----------------------------------------------------------------------===//
-
 namespace llvm {
 
 /// Note that you have to add:
 ///   DAG.addMutation(createAArch64MacroFusionDAGMutation());
 /// to AArch64PassConfig::createMachineScheduler() to have an effect.
 std::unique_ptr<ScheduleDAGMutation> createAArch64MacroFusionDAGMutation();
 
 } // llvm

lib/Target/AArch64/AArch64MacroFusion.cpp

 //===- AArch64MacroFusion.cpp - AArch64 Macro Fusion ----------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// \file This file contains the AArch64 implementation of the DAG scheduling mutation
-// to pair instructions back to back.
+/// \file This file contains the AArch64 implementation of the DAG scheduling
+///  mutation to pair instructions back to back.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AArch64MacroFusion.h"
 #include "AArch64Subtarget.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/Support/CommandLine.h"
+#include "llvm/CodeGen/MacroFusion.h"
 #include "llvm/Target/TargetInstrInfo.h"
 
-#define DEBUG_TYPE "misched"
-
-STATISTIC(NumFused, "Number of instr pairs fused");
-
 using namespace llvm;
 
-static cl::opt<bool> EnableMacroFusion("aarch64-misched-fusion", cl::Hidden,
-  cl::desc("Enable scheduling for macro fusion."), cl::init(true));
-
 namespace {
 
-/// \brief Verify that the instr pair, FirstMI and SecondMI, should be fused
-/// together.  Given an anchor instr, when the other instr is unspecified, then
-/// check if the anchor instr may be part of a fused pair at all.
+/// \brief Check if the instr pair, FirstMI and SecondMI, should be fused
+/// together. Given SecondMI, when FirstMI is unspecified, then check if
+/// SecondMI may be part of a fused pair at all.
 static bool shouldScheduleAdjacent(const TargetInstrInfo &TII,
                                    const TargetSubtargetInfo &TSI,
                                    const MachineInstr *FirstMI,
-                                   const MachineInstr *SecondMI) {
-  assert((FirstMI || SecondMI) && "At least one instr must be specified");
-
+                                   const MachineInstr &SecondMI) {
   const AArch64InstrInfo &II = static_cast<const AArch64InstrInfo&>(TII);
   const AArch64Subtarget &ST = static_cast<const AArch64Subtarget&>(TSI);
 
   // Assume wildcards for unspecified instrs.
   unsigned FirstOpcode =
     FirstMI ? FirstMI->getOpcode()
       : static_cast<unsigned>(AArch64::INSTRUCTION_LIST_END);
-  unsigned SecondOpcode =
-    SecondMI ? SecondMI->getOpcode()
-             : static_cast<unsigned>(AArch64::INSTRUCTION_LIST_END);
+  unsigned SecondOpcode = SecondMI.getOpcode();
 
   if (ST.hasArithmeticBccFusion())
     // Fuse CMN, CMP, TST followed by Bcc.
     if (SecondOpcode == AArch64::Bcc)
       switch (FirstOpcode) {
       default:
         return false;
       case AArch64::ADDSWri:
if (SecondOpcode == AArch64::CBNZW || SecondOpcode == AArch64::CBNZX ||
         // Shift value can be 0 making these behave like the "rr" variant...
         return !II.hasShiftedReg(*FirstMI);
       case AArch64::INSTRUCTION_LIST_END:
         return true;
       }
 
   if (ST.hasFuseAES())
     // Fuse AES crypto operations.
-    switch(FirstOpcode) {
+    switch(SecondOpcode) {
     // AES encode.
-    case AArch64::AESErr:
-      return SecondOpcode == AArch64::AESMCrr ||
-             SecondOpcode == AArch64::INSTRUCTION_LIST_END;
+    case AArch64::AESMCrr :
+      return FirstOpcode == AArch64::AESErr ||
+             FirstOpcode == AArch64::INSTRUCTION_LIST_END;
     // AES decode.
-    case AArch64::AESDrr:
-      return SecondOpcode == AArch64::AESIMCrr ||
-             SecondOpcode == AArch64::INSTRUCTION_LIST_END;
+    case AArch64::AESIMCrr:
+      return FirstOpcode == AArch64::AESDrr ||
+             FirstOpcode == AArch64::INSTRUCTION_LIST_END;
     }
 
   if (ST.hasFuseLiterals())
     // Fuse literal generation operations.
-    switch (FirstOpcode) {
+    switch (SecondOpcode) {
     // PC relative address.
-    case AArch64::ADRP:
-      return SecondOpcode == AArch64::ADDXri ||
-             SecondOpcode == AArch64::INSTRUCTION_LIST_END;
+    case AArch64::ADDXri:
+      return FirstOpcode == AArch64::ADRP ||
+             FirstOpcode == AArch64::INSTRUCTION_LIST_END;
     // 32 bit immediate.
-    case AArch64::MOVZWi:
-      return (SecondOpcode == AArch64::MOVKWi &&
-              SecondMI->getOperand(3).getImm() == 16) ||
-             SecondOpcode == AArch64::INSTRUCTION_LIST_END;
-    // Lower half of 64 bit immediate.
-    case AArch64::MOVZXi:
-      return (SecondOpcode == AArch64::MOVKXi &&
-              SecondMI->getOperand(3).getImm() == 16) ||
-             SecondOpcode == AArch64::INSTRUCTION_LIST_END;
-    // Upper half of 64 bit immediate.
+    case AArch64::MOVKWi:
+      return (FirstOpcode == AArch64::MOVZWi &&
+              SecondMI.getOperand(3).getImm() == 16) ||
+             FirstOpcode == AArch64::INSTRUCTION_LIST_END;
+    // Lower and upper half of 64 bit immediate.
     case AArch64::MOVKXi:
-      return FirstMI->getOperand(3).getImm() == 32 &&
-             ((SecondOpcode == AArch64::MOVKXi &&
-               SecondMI->getOperand(3).getImm() == 48) ||
-              SecondOpcode == AArch64::INSTRUCTION_LIST_END);
-    }
-
-  return false;
+      return FirstOpcode == AArch64::INSTRUCTION_LIST_END ||
+             (FirstOpcode == AArch64::MOVZXi &&
+              SecondMI.getOperand(3).getImm() == 16) ||
+             (FirstMI->getOperand(3).getImm() == 32 &&
+              FirstOpcode == AArch64::MOVKXi &&
+              SecondMI.getOperand(3).getImm() == 48);
     }
 
-/// \brief Implement the fusion of instr pairs in the scheduling DAG,
-/// anchored at the instr in AnchorSU..
-static bool scheduleAdjacentImpl(ScheduleDAGMI *DAG, SUnit &AnchorSU) {
-  const MachineInstr *AnchorMI = AnchorSU.getInstr();
-  if (!AnchorMI || AnchorMI->isPseudo() || AnchorMI->isTransient())
-    return false;
-
-  // If the anchor instr is the ExitSU, then consider its predecessors;
-  // otherwise, its successors.
-  bool Preds = (&AnchorSU == &DAG->ExitSU);
-  SmallVectorImpl<SDep> &AnchorDeps = Preds ? AnchorSU.Preds : AnchorSU.Succs;
-
-  const MachineInstr *FirstMI = Preds ? nullptr : AnchorMI;
-  const MachineInstr *SecondMI = Preds ? AnchorMI : nullptr;
-
-  // Check if the anchor instr may be fused.
-  if (!shouldScheduleAdjacent(*DAG->TII, DAG->MF.getSubtarget(),
-                              FirstMI, SecondMI))
-    return false;
-
-  // Explorer for fusion candidates among the dependencies of the anchor instr.
-  for (SDep &Dep : AnchorDeps) {
-    // Ignore dependencies that don't enforce ordering.
-    if (Dep.isWeak())
-      continue;
-
-    SUnit &DepSU = *Dep.getSUnit();
-    // Ignore the ExitSU if the dependents are successors.
-    if (!Preds && &DepSU == &DAG->ExitSU)
-      continue;
-
-    const MachineInstr *DepMI = DepSU.getInstr();
-    if (!DepMI || DepMI->isPseudo() || DepMI->isTransient())
-      continue;
-
-    FirstMI = Preds ? DepMI : AnchorMI;
-    SecondMI = Preds ? AnchorMI : DepMI;
-    if (!shouldScheduleAdjacent(*DAG->TII, DAG->MF.getSubtarget(),
-                                FirstMI, SecondMI))
-      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.
-    SUnit &FirstSU = Preds ? DepSU : AnchorSU;
-    SUnit &SecondSU = Preds ? AnchorSU : DepSU;
-    DAG->addEdge(&SecondSU, SDep(&FirstSU, SDep::Cluster));
-
-    // Adjust the latency between the anchor instr and its
-    // predecessors/successors.
-    for (SDep &IDep : AnchorDeps)
-      if (IDep.getSUnit() == &DepSU)
-        IDep.setLatency(0);
-
-    // Adjust the latency between the dependent instr and its
-    // successors/predecessors.
-    for (SDep &IDep : Preds ? DepSU.Succs : DepSU.Preds)
-      if (IDep.getSUnit() == &AnchorSU)
-        IDep.setLatency(0);
-
-    DEBUG(dbgs() << DAG->MF.getName() << "(): Macro fuse ";
-          FirstSU.print(dbgs(), DAG); dbgs() << " - ";
-          SecondSU.print(dbgs(), DAG); dbgs() << " /  ";
-          dbgs() << DAG->TII->getName(FirstMI->getOpcode()) << " - " <<
-                    DAG->TII->getName(SecondMI->getOpcode()) << '\n'; );
-
-    if (&SecondSU != &DAG->ExitSU)
-      // Make instructions dependent on FirstSU also dependent on SecondSU to
-      // prevent them from being scheduled between FirstSU and and SecondSU.
-      for (SUnit::const_succ_iterator
-             SI = FirstSU.Succs.begin(), SE = FirstSU.Succs.end();
-           SI != SE; ++SI) {
-        if (!SI->getSUnit() || SI->getSUnit() == &SecondSU)
-          continue;
-        DEBUG(dbgs() << "  Copy Succ ";
-              SI->getSUnit()->print(dbgs(), DAG); dbgs() << '\n';);
-        DAG->addEdge(SI->getSUnit(), SDep(&SecondSU, SDep::Artificial));
-      }
-
-    ++NumFused;
-    return true;
-  }
-
-  return false;
-}
-
-/// \brief Post-process the DAG to create cluster edges between instrs that may
-/// be fused by the processor into a single operation.
-class AArch64MacroFusion : public ScheduleDAGMutation {
-public:
-  AArch64MacroFusion() {}
-
-  void apply(ScheduleDAGInstrs *DAGInstrs) override;
-};
-
-void AArch64MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
-  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
-
-  // For each of the SUnits in the scheduling block, try to fuse the instr in it
-  // with one in its successors.
-  for (SUnit &ISU : DAG->SUnits)
-    scheduleAdjacentImpl(DAG, ISU);
-
-  // Try to fuse the instr in the ExitSU with one in its predecessors.
-  scheduleAdjacentImpl(DAG, DAG->ExitSU);
 }
 
 } // end namespace
 
 
 namespace llvm {
 
 std::unique_ptr<ScheduleDAGMutation> createAArch64MacroFusionDAGMutation () {
-  return EnableMacroFusion ? make_unique<AArch64MacroFusion>() : nullptr;
+  return createMacroFusionDAGMutation(shouldScheduleAdjacent);
 }
 
 } // end namespace llvm

lib/Target/X86/X86MacroFusion.h

 //===- X86MacroFusion.h - X86 Macro Fusion --------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
-// \file This file is distributed under the University of Illinois Open Source
+// This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains the X86 definition of the DAG scheduling mutation to pair
-// instructions back to back.
+/// \file This file contains the X86 definition of the DAG scheduling mutation
+///  to pair instructions back to back.
 //
 //===----------------------------------------------------------------------===//
 
-#include "X86InstrInfo.h"
 #include "llvm/CodeGen/MachineScheduler.h"
 
-//===----------------------------------------------------------------------===//
-// X86MacroFusion - DAG post-processing to encourage fusion of macro ops.
-//===----------------------------------------------------------------------===//
-
 namespace llvm {
 
 /// Note that you have to add:
 ///   DAG.addMutation(createX86MacroFusionDAGMutation());
 /// to X86PassConfig::createMachineScheduler() to have an effect.
 std::unique_ptr<ScheduleDAGMutation>
 createX86MacroFusionDAGMutation();
 
 } // end namespace llvm

lib/Target/X86/X86MacroFusion.cpp

 //===- X86MacroFusion.cpp - X86 Macro Fusion ------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
-// \file This file is distributed under the University of Illinois Open Source
+// This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains the X86 implementation of the DAG scheduling mutation to
-// pair instructions back to back.
+/// \file This file contains the X86 implementation of the DAG scheduling
+/// mutation to pair instructions back to back.
 //
 //===----------------------------------------------------------------------===//
 
 #include "X86MacroFusion.h"
 #include "X86Subtarget.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetInstrInfo.h"
-
-#define DEBUG_TYPE "misched"
-
-STATISTIC(NumFused, "Number of instr pairs fused");
+#include "llvm/CodeGen/MacroFusion.h"
 
 using namespace llvm;
 
-static cl::opt<bool> EnableMacroFusion("x86-misched-fusion", cl::Hidden,
-  cl::desc("Enable scheduling for macro fusion."), cl::init(true));
-
-namespace {
-
-/// \brief Verify that the instruction pair, First and 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 &ST,
-                                   const MachineInstr *First,
-                                   const MachineInstr *Second) {
+/// \brief Check if the instr pair, FirstMI and SecondMI, should be fused
+/// together. Given SecondMI, when FirstMI is unspecified, then check if
+/// SecondMI may be part of a fused pair at all.
+static bool shouldScheduleAdjacent(const TargetInstrInfo &TII,
+                                   const TargetSubtargetInfo &TSI,
+                                   const MachineInstr *FirstMI,
+                                   const MachineInstr &SecondMI) {
+  const X86Subtarget &ST = static_cast<const X86Subtarget&>(TSI);
   // 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 (!ST.hasAVX())
     return false;
 
   enum {
     FuseTest,
     FuseCmp,
     FuseInc
   } FuseKind;
 
-  assert((First || Second) && "At least one instr must be specified");
-  unsigned FirstOpcode = First
-                         ? First->getOpcode()
-                         : static_cast<unsigned>(X86::INSTRUCTION_LIST_END);
-  unsigned SecondOpcode = Second
-                          ? Second->getOpcode()
-                          : static_cast<unsigned>(X86::INSTRUCTION_LIST_END);
+  unsigned FirstOpcode = FirstMI
+                         ? FirstMI->getOpcode()
+  unsigned SecondOpcode = SecondMI.getOpcode();
 
   switch (SecondOpcode) {
   default:
     return false;
   case X86::JE_1:
   case X86::JNE_1:
   case X86::JL_1:
   case X86::JLE_1:
static bool shouldScheduleAdjacent(const TargetInstrInfo &TII,
   case X86::DEC64r:
   case X86::DEC8r:
     return FuseKind == FuseInc;
   case X86::INSTRUCTION_LIST_END:
     return true;
   }
 }
 
-/// \brief Post-process the DAG to create cluster edges between instructions
-/// that may be fused by the processor into a single operation.
-class X86MacroFusion : public ScheduleDAGMutation {
-public:
-  X86MacroFusion() {}
-
-  void apply(ScheduleDAGInstrs *DAGInstrs) override;
-};
-
-void X86MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
-  ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
-  const X86Subtarget &ST = DAG->MF.getSubtarget<X86Subtarget>();
-
-  // For now, assume targets can only fuse with the branch.
-  SUnit &ExitSU = DAG->ExitSU;
-  MachineInstr *Branch = ExitSU.getInstr();
-  if (!Branch || !shouldScheduleAdjacent(ST, nullptr, Branch))
-    return;
-
-  for (SDep &PredDep : ExitSU.Preds) {
-    if (PredDep.isWeak())
-      continue;
-    SUnit &SU = *PredDep.getSUnit();
-    MachineInstr &Pred = *SU.getInstr();
-    if (!shouldScheduleAdjacent(ST, &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);
-
-    ++NumFused;
-    DEBUG(dbgs() << DAG->MF.getName() << "(): Macro fuse ";
-          SU.print(dbgs(), DAG);
-          dbgs() << " - ExitSU"
-                 << " / " << DAG->TII->getName(Pred.getOpcode()) << " - "
-                 << DAG->TII->getName(Branch->getOpcode()) << '\n';);
-
-    break;
-  }
-}
-
-} // end namespace
-
 namespace llvm {
 
 std::unique_ptr<ScheduleDAGMutation>
 createX86MacroFusionDAGMutation () {
-  return EnableMacroFusion ? make_unique<X86MacroFusion>() : nullptr;
+  return createBranchMacroFusionDAGMutation(shouldScheduleAdjacent);
 }
 
 } // end namespace llvm