[X86MacroFusion] Handle branch fusion (AMD CPUs).

[courbet]

Summary

This adds a BranchFusion feature to replace the usage of the MacroFusion
for AMD CPUs.

See D59688 for context.

[courbet]

clang-format

[lebedev.ri]

Looks good.
Can there be a test that we don't fuse non-CMP/TEST instructions if we only have branchfusion?

llvm/lib/Target/X86/X86.td

347–359

I think it would be better to swap these around?
FeatureMacroFusion is a superset of FeatureBranchFusion.
(maybe even inherit FeatureBranchFusion by FeatureMacroFusion, not sure it is possible here.)

354

// Bulldozer and newer processors can merge CMP/TEST (but not other instructions)
// with conditional branches.

[lebedev.ri]

llvm/test/Transforms/LoopStrengthReduce/X86/macro-fuse-cmp.ll

2

Also, if you do add a test that we don't fuse non-CMP/TEST instructions if we only have branchfusion,
could you please also add a bdver2 runline, and precommit all that?

[courbet]

Add tests.

[courbet]

Update comment, swap features.

llvm/lib/Target/X86/X86.td

347–359

I'd rather not inherit because they are actually different (e.g. w.r.t. CMP). Also they have different subtle limitations that are not currently modeled (see Agner), but we might want to model in the future.

[lebedev.ri]

Looks good to me, but please wait a bit for @andreadb.

llvm/lib/Target/X86/X86.td

347–359

Sounds good.

llvm/lib/Target/X86/X86MacroFusion.cpp

23–30

FirstInstrKind?

32–37

JumpKind?

llvm/test/CodeGen/X86/testb-je-fusion.ll

1–3 ↗

(On Diff #192479)

In trunk, i think you will get slightly more meaningful diff with

; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
; RUN: llc < %s -mtriple=x86_64-- -mattr=-macrofusion,-branchfusion | FileCheck %s --check-prefixes=NOFUSION
; RUN: llc < %s -mtriple=x86_64-- -mattr=-macrofusion,+branchfusion | FileCheck %s --check-prefixes=NOFUSION,BRANCHFUSION,BRANCHFUSIONONLY
; RUN: llc < %s -mtriple=x86_64-- -mattr=+macrofusion,-branchfusion | FileCheck %s --check-prefixes=NOFUSION,BRANCHFUSION,MACROFUSION

(drop [+-]branchfusion for trunk, add it back in patch)

[RKSimon]

Some style changes

llvm/lib/Target/X86/X86MacroFusion.cpp

36

(style) Please comment enums - they are not obvious.

173

Add a unreachable message

llvm/lib/Target/X86/X86TargetTransformInfo.h

91

NFC change - commit separetely

[andreadb]

Macro-op fusion on Intel processors is essentially a form branch fusion.
The only difference in practice is that - starting from Sandybridge - a few extra opcodes (mostly arithmetic) other than CMP/TEST can now be fuse with branches.
But conceptually, what AMD calls branch fusion is (a form of) macro-op fusion.
Using FeatureMacroFusion and FeatureBranchFusion to refer to the two different forms of macro-op fusion may be a bit misleading... But then, I am not good with names, so I am not sure I am able to suggest better names for those :-( .

What if in future Intel/AMD processors decide to further expand the set of opcodes that are subject to macro-op fusion? If we adopt this approach, then we end up with even more feature flags. whether that is acceptable or not is often a matter of tastes. It may not be a problem for now (we only have two flags). However, we should really look into a tablegen-driven approach. For example, every scheduling model could declare the set of opcodes that can be fused with branches. Note that we can already do something like that today if we use STIPRedicateDecl and STIPredicate definitions via tablegen (with the advantage that the information is also accessible at the MC layer - and tools like mca could use it..).

In case I can help you with how to write those STIPredicate.

But for the short term, I think this patch is fine.
We may try to revisit this approach in future if we decide to get rid of those target features entirely, and expose that info to the MC layer (https://bugs.llvm.org/show_bug.cgi?id=36670).

-Andrea

[courbet]

Address review comments, rebase.

llvm/test/CodeGen/X86/testb-je-fusion.ll

1–3 ↗

(On Diff #192479)

Good point, done.

[lebedev.ri]

Perfect, thanks!

[courbet]

Thanks for the review.

llvm/lib/Target/X86/X86.td

 // Development Manual. This feature essentially means that REP MOVSB will copy
 // using the largest available size instead of copying bytes one by one, making
 // it at least as fast as REPMOVS{W,D,Q}.
 def FeatureERMSB
     : SubtargetFeature<
           "ermsb", "HasERMSB", "true",
           "REP MOVS/STOS are fast">;
 
 // Sandy Bridge and newer processors have many instructions that can be
 // fused with conditional branches and pass through the CPU as a single
 // operation.
 def FeatureMacroFusion
     : SubtargetFeature<"macrofusion", "HasMacroFusion", "true",
                  "Various instructions can be fused with conditional branches">;
 
+// Bulldozer and newer processors can merge CMP/TEST with conditional branches.
+def FeatureBranchFusion
+    : SubtargetFeature<"branchfusion", "HasBranchFusion", "true",
+                 "CMP/TEST can be fused with conditional branches">;
+
 // Gather is available since Haswell (AVX2 set). So technically, we can
 // generate Gathers on all AVX2 processors. But the overhead on HSW is high.
 // Skylake Client processor has faster Gathers than HSW and performance is
 // similar to Skylake Server (AVX-512).
 def FeatureHasFastGather
     : SubtargetFeature<"fast-gather", "HasFastGather", "true",
                        "Indicates if gather is reasonably fast">;
 
 def FeaturePrefer256Bit
list<SubtargetFeature> BdVer1InheritableFeatures = [FeatureX87,
                                                       FeatureNOPL,
                                                       FeatureLZCNT,
                                                       FeaturePOPCNT,
                                                       FeatureXSAVE,
                                                       FeatureLWP,
                                                       FeatureSlowSHLD,
                                                       FeatureLAHFSAHF,
                                                       FeatureFast11ByteNOP,
-                                                      FeatureMacroFusion];
+                                                      FeatureBranchFusion];
   list<SubtargetFeature> BdVer1Features = BdVer1InheritableFeatures;
 
   // PileDriver
   list<SubtargetFeature> BdVer2AdditionalFeatures = [FeatureF16C,
                                                      FeatureBMI,
                                                      FeatureTBM,
                                                      FeatureFMA,
                                                      FeatureFastBEXTR];
list<SubtargetFeature> ZNFeatures = [FeatureADX,
                                        FeatureFSGSBase,
                                        FeatureFXSR,
                                        FeatureNOPL,
                                        FeatureFastLZCNT,
                                        FeatureLAHFSAHF,
                                        FeatureLZCNT,
                                        FeatureFastBEXTR,
                                        FeatureFast15ByteNOP,
-                                       FeatureMacroFusion,
+                                       FeatureBranchFusion,
                                        FeatureMMX,
                                        FeatureMOVBE,
                                        FeatureMWAITX,
                                        FeaturePCLMUL,
                                        FeaturePOPCNT,
                                        FeaturePRFCHW,
                                        FeatureRDRAND,
                                        FeatureRDSEED,

llvm/lib/Target/X86/X86MacroFusion.cpp

 
 #include "X86MacroFusion.h"
 #include "X86Subtarget.h"
 #include "llvm/CodeGen/MacroFusion.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 
 using namespace llvm;
 
-/// 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.
-  if (!ST.hasMacroFusion())
-    return false;
+namespace {
 
-  enum {
-    FuseTest,
-    FuseCmp,
-    FuseInc
-  } FuseKind;
-
-  unsigned FirstOpcode = FirstMI
-                         ? FirstMI->getOpcode()
-                         : static_cast<unsigned>(X86::INSTRUCTION_LIST_END);
-  unsigned SecondOpcode = SecondMI.getOpcode();
+enum class FirstKind {
+  Test,
+  Cmp,
+  And,
+  ALU,
+  IncDec,
+  Invalid
+};
+
+enum class SecondKind {
+  ELG,
+  AB,
+  SPO,
+  Invalid,
+};
 
-  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:
-    FuseKind = FuseInc;
-    break;
-  case X86::JB_1:
-  case X86::JBE_1:
-  case X86::JA_1:
-  case X86::JAE_1:
-    FuseKind = FuseCmp;
-    break;
-  case X86::JS_1:
-  case X86::JNS_1:
-  case X86::JP_1:
-  case X86::JNP_1:
-  case X86::JO_1:
-  case X86::JNO_1:
-    FuseKind = FuseTest;
-    break;
-  }
+}  // namespace
 
-  switch (FirstOpcode) {
+static FirstKind classifyFirst(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
   default:
-    return false;
+    return FirstKind::Invalid;
   case X86::TEST8rr:
   case X86::TEST16rr:
   case X86::TEST32rr:
   case X86::TEST64rr:
   case X86::TEST8ri:
   case X86::TEST16ri:
   case X86::TEST32ri:
   case X86::TEST64ri32:
   case X86::TEST8mr:
   case X86::TEST16mr:
   case X86::TEST32mr:
   case X86::TEST64mr:
+    return FirstKind::Test;
   case X86::AND16ri:
   case X86::AND16ri8:
   case X86::AND16rm:
   case X86::AND16rr:
   case X86::AND32ri:
   case X86::AND32ri8:
   case X86::AND32rm:
   case X86::AND32rr:
   case X86::AND64ri32:
   case X86::AND64ri8:
   case X86::AND64rm:
   case X86::AND64rr:
   case X86::AND8ri:
   case X86::AND8rm:
   case X86::AND8rr:
-    return true;
+    return FirstKind::And;
   case X86::CMP16ri:
   case X86::CMP16ri8:
   case X86::CMP16rm:
   case X86::CMP16rr:
   case X86::CMP16mr:
   case X86::CMP32ri:
   case X86::CMP32ri8:
   case X86::CMP32rm:
   case X86::CMP32rr:
   case X86::CMP32mr:
   case X86::CMP64ri32:
   case X86::CMP64ri8:
   case X86::CMP64rm:
   case X86::CMP64rr:
   case X86::CMP64mr:
   case X86::CMP8ri:
   case X86::CMP8rm:
   case X86::CMP8rr:
   case X86::CMP8mr:
+    return FirstKind::Cmp;
   case X86::ADD16ri:
   case X86::ADD16ri8:
   case X86::ADD16ri8_DB:
   case X86::ADD16ri_DB:
   case X86::ADD16rm:
   case X86::ADD16rr:
   case X86::ADD16rr_DB:
   case X86::ADD32ri:
static FirstKind classifyFirst(const MachineInstr &MI) {
   case X86::SUB32rr:
   case X86::SUB64ri32:
   case X86::SUB64ri8:
   case X86::SUB64rm:
   case X86::SUB64rr:
   case X86::SUB8ri:
   case X86::SUB8rm:
   case X86::SUB8rr:
-    return FuseKind == FuseCmp || FuseKind == FuseInc;
+    return FirstKind::ALU;
   case X86::INC16r:
   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 FirstKind::IncDec;
+  }
+}
+
+static SecondKind classifySecond(const MachineInstr &MI) {
+  switch (MI.getOpcode()) {
+  default:
+    return SecondKind::Invalid;
+  case X86::JE_1:
+  case X86::JNE_1:
+  case X86::JL_1:
+  case X86::JLE_1:
+  case X86::JG_1:
+  case X86::JGE_1:
+    return SecondKind::ELG;
+  case X86::JB_1:
+  case X86::JBE_1:
+  case X86::JA_1:
+  case X86::JAE_1:
+    return SecondKind::AB;
+  case X86::JS_1:
+  case X86::JNS_1:
+  case X86::JP_1:
+  case X86::JNP_1:
+  case X86::JO_1:
+  case X86::JNO_1:
+    return SecondKind::SPO;
+  }
+}
+
+/// 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 any kind of fusion.
+  if (!(ST.hasBranchFusion() || ST.hasMacroFusion()))
+    return false;
+
+  const SecondKind BranchKind = classifySecond(SecondMI);
+
+  if (BranchKind == SecondKind::Invalid)
+    return false; // Second cannot be fused with anything.
+
+  if (FirstMI == nullptr)
+    return true;  // We're only checking whether Second can be fused at all.
+
+  const FirstKind TestKind = classifyFirst(*FirstMI);
+
+  if (ST.hasBranchFusion()) {
+    // Branch fusion can merge CMP and TEST with all conditional jumps.
+    return (TestKind == FirstKind::Cmp || TestKind == FirstKind::Test);
+  }
+
+  if (ST.hasMacroFusion()) {
+    // Macro Fusion rules are a bit more complex. See Agner Fog's
+    // Microarchitecture table 9.2 "Instruction Fusion".
+    switch (TestKind) {
+      case FirstKind::Test:
+      case FirstKind::And:
         return true;
+      case FirstKind::Cmp:
+      case FirstKind::ALU:
+        return BranchKind == SecondKind::ELG || BranchKind == SecondKind::AB;
+      case FirstKind::IncDec:
+        return BranchKind == SecondKind::ELG;
+      case FirstKind::Invalid:
+        return false;
     }
   }
 
+  llvm_unreachable("");
+}
+
 namespace llvm {
 
 std::unique_ptr<ScheduleDAGMutation>
 createX86MacroFusionDAGMutation () {
   return createBranchMacroFusionDAGMutation(shouldScheduleAdjacent);
 }
 
 } // end namespace llvm

llvm/lib/Target/X86/X86Subtarget.h

protected:
   bool HasFastLZCNT = false;
 
   /// True if SHLD based rotate is fast.
   bool HasFastSHLDRotate = false;
 
   /// True if the processor supports macrofusion.
   bool HasMacroFusion = false;
 
+  /// True if the processor supports branch fusion.
+  bool HasBranchFusion = false;
+
   /// True if the processor has enhanced REP MOVSB/STOSB.
   bool HasERMSB = false;
 
   /// True if the short functions should be padded to prevent
   /// a stall when returning too early.
   bool PadShortFunctions = false;
 
   /// True if two memory operand instructions should use a temporary register
public:
   bool hasFastGather() const { return HasFastGather; }
   bool hasFastScalarFSQRT() const { return HasFastScalarFSQRT; }
   bool hasFastVectorFSQRT() const { return HasFastVectorFSQRT; }
   bool hasFastLZCNT() const { return HasFastLZCNT; }
   bool hasFastSHLDRotate() const { return HasFastSHLDRotate; }
   bool hasFastBEXTR() const { return HasFastBEXTR; }
   bool hasFastHorizontalOps() const { return HasFastHorizontalOps; }
   bool hasMacroFusion() const { return HasMacroFusion; }
+  bool hasBranchFusion() const { return HasBranchFusion; }
   bool hasERMSB() const { return HasERMSB; }
   bool hasSlowDivide32() const { return HasSlowDivide32; }
   bool hasSlowDivide64() const { return HasSlowDivide64; }
   bool padShortFunctions() const { return PadShortFunctions; }
   bool slowTwoMemOps() const { return SlowTwoMemOps; }
   bool LEAusesAG() const { return LEAUsesAG; }
   bool slowLEA() const { return SlowLEA; }
   bool slow3OpsLEA() const { return Slow3OpsLEA; }

llvm/lib/Target/X86/X86TargetTransformInfo.h

const FeatureBitset InlineFeatureIgnoreList = {
     X86::FeatureFastScalarFSQRT,
     X86::FeatureFastSHLDRotate,
     X86::FeatureFastVariableShuffle,
     X86::FeatureFastVectorFSQRT,
     X86::FeatureLEAForSP,
     X86::FeatureLEAUsesAG,
     X86::FeatureLZCNTFalseDeps,
     X86::FeatureMacroFusion,
+    X86::FeatureBranchFusion,
     X86::FeatureMergeToThreeWayBranch,
     X86::FeaturePadShortFunctions,
     X86::FeaturePOPCNTFalseDeps,
     X86::FeatureSSEUnalignedMem,
     X86::FeatureSlow3OpsLEA,
     X86::FeatureSlowDivide32,
     X86::FeatureSlowDivide64,
     X86::FeatureSlowIncDec,
const FeatureBitset InlineFeatureIgnoreList = {
     X86::FeaturePrefer256Bit,
 
     // CPU name enums. These just follow CPU string.
     X86::ProcIntelAtom,
     X86::ProcIntelGLM,
     X86::ProcIntelGLP,
     X86::ProcIntelSLM,
     X86::ProcIntelTRM,
   };
 
 public:
   explicit X86TTIImpl(const X86TargetMachine *TM, const Function &F)
       : BaseT(TM, F.getParent()->getDataLayout()), ST(TM->getSubtargetImpl(F)),
         TLI(ST->getTargetLowering()) {}
 
   /// \name Scalar TTI Implementations
   /// @{

llvm/lib/Target/X86/X86TargetTransformInfo.cpp

return std::tie(C1.Insns, C1.NumRegs, C1.AddRecCost,
                     C1.NumIVMuls, C1.NumBaseAdds,
                     C1.ScaleCost, C1.ImmCost, C1.SetupCost) <
            std::tie(C2.Insns, C2.NumRegs, C2.AddRecCost,
                     C2.NumIVMuls, C2.NumBaseAdds,
                     C2.ScaleCost, C2.ImmCost, C2.SetupCost);
 }
 
 bool X86TTIImpl::canMacroFuseCmp() {
-  return ST->hasMacroFusion();
+  return ST->hasMacroFusion() || ST->hasBranchFusion();
 }
 
 bool X86TTIImpl::isLegalMaskedLoad(Type *DataTy) {
   if (!ST->hasAVX())
     return false;
 
   // The backend can't handle a single element vector.
   if (isa<VectorType>(DataTy) && DataTy->getVectorNumElements() == 1)

llvm/test/Transforms/LoopStrengthReduce/X86/macro-fuse-cmp.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: opt < %s -loop-reduce -mcpu=btver2  -S | FileCheck %s --check-prefix=JAG
 ; RUN: opt < %s -loop-reduce -mcpu=haswell -S | FileCheck %s --check-prefix=HSW
 
-; RUN: llc < %s                    | FileCheck %s --check-prefix=BASE
-; RUN: llc < %s -mattr=macrofusion | FileCheck %s --check-prefix=FUSE
+; RUN: llc < %s                     | FileCheck %s --check-prefix=BASE
+; RUN: llc < %s -mattr=macrofusion  | FileCheck %s --check-prefix=FUSE
+; RUN: llc < %s -mattr=branchfusion | FileCheck %s --check-prefix=FUSE
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-unknown"
 
 ; PR35681 - https://bugs.llvm.org/show_bug.cgi?id=35681
 ; FIXME: If a CPU can macro-fuse a compare and branch, then we discount that
 ; cost in LSR and avoid generating large offsets in each memory access.
 ; This reduces code size and may improve decode throughput.