[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 ↗

(On Diff #86350)

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/lib/CodeGen/MachineScheduler.cpp

 /// 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;
+
+private:
+  bool applyImpl(ScheduleDAGMI *DAG, SUnit *ASU, SmallVectorImpl<SDep> &APreds,
+                 bool Preds);
 };
 } // 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 each of the block SUnits, iterate over its successors.
+  for (SUnit &ASU : DAG->SUnits)
+    applyImpl(DAG, &ASU, ASU.Succs, false);
+
+  // Iterate over the predecessors of ExitSU.
+  applyImpl(DAG, &DAG->ExitSU, DAG->ExitSU.Preds, true);
+}
 
-  for (SDep &PredDep : ExitSU.Preds) {
-    if (PredDep.isWeak())
-      continue;
-    SUnit &SU = *PredDep.getSUnit();
-    MachineInstr &Pred = *SU.getInstr();
-    if (!TII.shouldScheduleAdjacent(Pred, *Branch))
+bool MacroFusion::applyImpl(ScheduleDAGMI *DAG, SUnit *ASU,
+                            SmallVectorImpl<SDep> &APreds, bool Preds) {
+  const MachineInstr *AMI = ASU->getInstr();
+  if (!AMI || AMI->isPseudo() || AMI->isTransient())
+    return false;
+
+  for (SDep &BDep : APreds) {
+    if (BDep.isWeak())
       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");
+    SUnit *BSU = BDep.getSUnit();
+    const MachineInstr *BMI = BSU->getInstr();
+    if (!BMI || BMI->isPseudo() || BMI->isTransient() ||
+        !TII.shouldScheduleAdjacent(*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.
+    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.
+    SmallVectorImpl<SDep> &BSuccs = Preds ? BSU->Succs : BSU->Preds;
+    for (SDep &Dep : BSuccs)
+      if (Dep.getSUnit() == ASU)
+        Dep.setLatency(0);
 
-    // 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 "; ASU->print(dbgs(), DAG); dbgs() << " - ";
+                                   BSU->print(dbgs(), DAG); dbgs() << '\n');
+    return true;
 
-    DEBUG(dbgs() << "Macro Fuse SU(" << SU.NodeNum << ")\n");
-    break;
-  }
+  return false;
 }
 
 //===----------------------------------------------------------------------===//
 // 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